First, find a prefix-sum on each column (O(N^2)). This is done so that we can later on compute the sum of consecutive rows in O(1) complexity.
Now, observe all possible row-pairs (O(N^2)), and for each pair, you can see that we can get the sum of each "column" in O(1) complexity. This will provide us with a feeling that you can view the contiguous rows within each row-pair as only one row per column. Thus, we have a somewhat a one-dimensional array of column sums. To find the maximum contiguous elements in one-dimensional array, there is a Kadane's algorithm which is O(N). All the steps above gives O(N^3) algorithm. -Lego On 3/12/07, Balachander <[EMAIL PROTECTED]> wrote: > > > How to find the Rectangle of Max sum in a 2D matrix consisting of both > +ve and -ve numbers,,, > > Logic needed .. > No brute Force pls... > > > > > -- Fear of the LORD is the beginning of knowledge (Proverbs 1:7) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
