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,,, >
This solution is based on a similar variant of the problem, calculating maximum contiguous sub-array in one dimension. That problem can be solved in O(n) time (time linear to the size of the input array). For an array of dimensions m x n, the rectangle of maximum sum can be computed in O(m^2 * n). The idea is as follows, (A) Along one dimension calculate the cummulative sums, That yields, For each j, CUMM[i][j] = A[1][j] + ... + A[n][j] This step calculates the CUMM[][] array in O(m * n) Having done this we can for any sub-array along this dimension answer queries of the form Sum(A[i1][j] to A[i2][j]) in O(1) time. This is required for the next step. (B) For each pair of start and end points along the precalculated dimension, perform a linear scan similar to the one dimensional version of the problem along the other dimension. The pairs enumerable will work out to O(m*m) and the sweep will be O(n). (Made possible with the help of the precalcuation in the previous step). -- Regards, Rajiv Mathews --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
