CODEWITHSUNDEEP
algorithmmatrix
Mohammad Moghimi
Mohammad Moghimi

Reputation: 4686

Maximum sum/area submatrix

Input: nxn matrix of postitive/negative numbers and k.

Output: submatrix with maximum sum of its elements divided by its number of elements that has at least k elements.

Is there any algorithm better than O(n^4) for this problem?

Upvotes: 1

Views: 802

Answers (2)

thearn
thearn

Reputation: 323

An FFT-based divide-and-conquer approach to this problem:

https://github.com/thearn/maximum-submatrix-sum

It's not as efficient as Kadane's, (O(N^3) vs. O(N^3 log N)) but does give a different take on solution construction.

Upvotes: 1

user2566092
user2566092

Reputation: 4661

There is a O(n^3) 2-d kadane algorithm for finding the maximum sum submatrix (i.e. subrectangle) in an nxn matrix. (You can find posts on SO about it, or read online). Once you understand how the algorithm works, it is clear that you can get an O(n^3) time solution for your problem if you can solve the problem of finding a maximum average subinterval of length at least m in a 1-d array of n numbers in O(n) time. This is indeed possible, see the paper cs.slu.edu/~goldwasser/publications/DensityPreprint.pdf

Thus there is an O(n^3) time solution for your problem.

Upvotes: 0

Related Questions