Menu
Bentley's Programming Pearls (2nd ed.), in the chapter about the maximum subarray problem, describes its two-dimensional version:
...we are given an n × n array of reals, and we must find the maximum sum contained in any rectangular subarray. What is the complexity of this problem?
Bentley mentions that, as of the book's publication date (2000), the problem of finding an optimal solution was open.
Is it still so? Which is the best known solution? Any pointer to recent literature?
798
We basically find top and bottom row numbers (which have maximum sum) for every fixed left and right column pair. To find the top and bottom row numbers, calculate the sum of elements in every row from left to right and store these sums in an array say temp[].
Simple Approach: Run a loop for i from 0 to n – 1, where n is the size of the array. Now, we will run a nested loop for j from i to n – 1 and add the value of the element at index j to a variable currentMax. Lastly, for every subarray, we will check if the currentMax is the maximum sum of all contiguous subarrays.
Don't be afraid this is not very difficult.... For new programmer, this is very essential... We know a little bit for that we don't answer many problem as like "largest sum contiguous sub array" that's really very easy to determine largest sum if we know the following algorithm.....
Generally speaking, the first solution that comes to mind is to calculate the sum of every possible subarray and return the one with the maximum sum. So we'll start at index 0 and add every element to the running sum in the iteration. We'll also keep track of the maximum sum seen so far.
The 1D solution to this problem (the maximal sub-array) is Theta(n) using an algorithm called "Kadane's Algorithm" (there are other algorithms I'm sure, but I have personal experience with this one). The 2D solution to this problem (the maximal sub-rectangle) is known to be O(n^3) using an implementation of Kadane's Algorithm (again I'm sure there's others, but I've used this before).
Although we know that the 2D solution can be found in Theta(n^3), no one has been able to prove whether or not n^3 is the lower bound. For many algorithms, when you increase a dimension you increase the lower bound on the algorithm by a constant magnitude. With this particular problem the complexity doesn't increase linearly, and therefore there is no known solution to work for any given dimension, thus the problem is still open.
In reference to a similar case: we know that 2 matrices can be multiplied together in n^3 time. There is also an algorithm out there that can do it in n^2.8 I believe. However, there is no math indicating that we can't get it lower than n^2.8, so it's still an "open" algorithm.
114
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
