CODEWITHSUNDEEP
algorithmdynamic-programmingsubmatrix
Khurshid
Khurshid

Reputation: 2724

Maximal sum of submatrix NxN matrix and with N-nonzero values, only O(N^2)

Suppose you have an N × N matrix where each row has exactly one nonzero element and each column has exactly one nonzero element (the nonzero elements can be either positive or negative). We want to find the maximum-sum submatrix. How efficiently can we do so?

The matrix has dimension N × N and only N non-zero elements. N is so big, so I can't use an O(N3) algorithm. Does anyone know how to solve this in time O(N2), O(N log N), or some other time complexity like this?

Thanks!

Upvotes: 4

Views: 985

Answers (1)

user2566092
user2566092

Reputation: 4661

If you want to find the maximum sum subrectangle, you can do it in O(n^2 log n) time using the algorithm described here maximum sum subrectangle in a sparse matrix . This beats Kadane's algorithm which is O(n^3).

Upvotes: 2

Related Questions