[algogeeks] Re: To find a rectangle of max sum
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 -~--~~~~--~~--~--~---
[algogeeks] Re: To find a rectangle of max sum
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 -~--~~~~--~~--~--~---
[algogeeks] Re: To find a rectangle of max sum
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,,, Is any one aware of any theoretical lower bounds on this problem? I remember reading about this in ``Programming Pearls'' by Jon Bentley, where he had mentioned that the O(m^2 * n) bound was the best any one had done back then. I realize now that ``Programming Pearls'' are pretty outdated and was wondering if any one is aware of anything that has bettered this? -- 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 -~--~~~~--~~--~--~---
[algogeeks] Re: To find a rectangle of max sum
Another variant...(or rather wanted to say in my previous post) How do you find a maximum square of all ones in a binary matrix of 0s and 1s? --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
