Two-dimensional maximum subarray

Bentley's Programming Pearls (2nd ed.), 开发者_如何学Cin 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?

---

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.

---

   // Program to find maximum sum subarray in a given 2D array
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define ROW 4
#define COL 5

  // Implementation of Kadane's algorithm for 1D array. The function returns the
// maximum sum and stores starting and ending indexes of the maximum sum subarray
// at addresses pointed by start and finish pointers respectively.
int kadane(int* arr, int* start, int* finish, int n)
{
// initialize sum, maxSum and
int sum = 0, maxSum = INT_MIN, i;

// Just some initial value to check for all negative values case
*finish = -1;

// local variable
int local_start = 0;

for (i = 0; i < n; ++i)
{
    sum += arr[i];
    if (sum < 0)
    {
        sum = 0;
        local_start = i+1;
    }
    else if (sum > maxSum)
    {
        maxSum = sum;
        *start = local_start;
        *finish = i;
    }
}

 // There is at-least one non-negative number
if (*finish != -1)
    return maxSum;

// Special Case: When all numbers in arr[] are negative
maxSum = arr[0];
*start = *finish = 0;

// Find the maximum element in array
for (i = 1; i < n; i++)
{
    if (arr[i] > maxSum)
    {
        maxSum = arr[i];
        *start = *finish = i;
    }
   }
   return maxSum;
 }

 // The main function that finds maximum sum rectangle in M[][]
  void findMaxSum(int M[][COL])
 {
 // Variables to store the final output
 int maxSum = INT_MIN, finalLeft, finalRight, finalTop, finalBottom;

 int left, right, i;
 int temp[ROW], sum, start, finish;

  // Set the left column
   for (left = 0; left < COL; ++left)
  {
     // Initialize all elements of temp as 0
    memset(temp, 0, sizeof(temp));

    // Set the right column for the left column set by outer loop
    for (right = left; right < COL; ++right)
    {
        // Calculate sum between current left and right for every row 'i'
        for (i = 0; i < ROW; ++i)
            temp[i] += M[i][right];

        // Find the maximum sum subarray in temp[]. The kadane() function
        // also sets values of start and finish.  So 'sum' is sum of
        // rectangle between (start, left) and (finish, right) which is the
        //  maximum sum with boundary columns strictly as left and right.
        sum = kadane(temp, &start, &finish, ROW);

        // Compare sum with maximum sum so far. If sum is more, then update
        // maxSum and other output values
        if (sum > maxSum)
        {
            maxSum = sum;
            finalLeft = left;
            finalRight = right;
            finalTop = start;
            finalBottom = finish;
        }
     }
   }

  // Print final values
  printf("(Top, Left) (%d, %d)\n", finalTop, finalLeft);
  printf("(Bottom, Right) (%d, %d)\n", finalBottom, finalRight);
  printf("Max sum is: %d\n", maxSum);
  }

  // Driver program to test above functions
  int main()
  {
  int M[ROW][COL] = {{1, 2, -1, -4, -20},
                   {-8, -3, 4, 2, 1},
                   {3, 8, 10, 1, 3},
                   {-4, -1, 1, 7, -6}
                  };

  findMaxSum(M);

 return 0;
 }


  ////////I found this program , hope it will help you

---

FYI, the new edition of the book has an answer, but it is so vague, I don't know what it would entail.

In any case, I would use divide and conquer + dynamic programming to solve this. Let's define MaxSum(x, y) as the maximum sum of any subarray inside the rectangle bounded by the top-left most corner of the N X N array, with height y and width x. (so the answer to the question would be in MaxSum(n-1, n-1))

MaxSum(x, y) is the max between:
1) MaxSum(x, y-1)
2) MaxSum(x-1, y)
3) Array[x, y] (the number in this N X N array for this specific location)
4) MaxEnding(x, y-1) + SUM of all elements from Array[MaxEndingXStart(x, y-1), y] to Array[x, y]
5) MaxEnding(x-1, y) + SUM of all elements from Array[x, MaxEndingYStart(x-1, y)] to Array[x, y]

MaxEnding(x, y-1) is the maximum sum of any subarray that INCLUDES the # in Array[x, y-1]. Likewise, MaxEnding(x-1, y) is the maximum sum of any subarray that INCLUDES the # in Array[x-1, y]. MaxEndingXStart(x, y-1) is the STARTING x coordinate of the subarray that has the maximum sum of any subarray that INCLUDEs the # in Array[x, y-1]. MaxEndingYStart (x-1, y) is the STARTING y coordinate of the subarray that has the maximum sum of any subarray that INCLUDES the # in Array[x-1, y].

The 2 sum's in #4 and #5 below can be computed easily by keeping the sum of all elements encountered in a specific row, as you go through each column, then subtracting 2 sums to get the sum for a specific section.

To implement this, you would need to do a bottom-up approach, since you need to compute Max(x, y-1), Max(x-1, y), MaxEnding(x, y-1), and MaxEnding(x-1, y).. so you can do lookups when you compute MaxEnding(x, y).

//first do some preprocessing and store Max(0, i) for all i from 0 to n-1.
//and store Max(i, 0) for all i from 0 to n-1.

for(int i =1; i < n; i++){
   for(int j=1; j < n; j++) {
      //LOGIC HERE
   }
}