二维最大子数组

Question

Bentley 的Programming Pearls（第二版）在有关最大子数组问题的章节中描述了其二维版本：

...我们有一个 n × n 实数数组，我们必须找到任何矩形子数组中包含的最大和。这个问题的复杂性是多少？

Bentley 提到，截至该书出版之日（2000 年），寻找最佳解决方案的问题尚未解决。
现在还是这样吗？哪个是最著名的解决方案？有最近的文献吗？

Answer 1

这个问题（最大子数组）的一维解决方案是 Theta(n)，使用一种名为“Kadane 算法”的算法（我确信还有其他算法，但我对此有个人经验）。使用 Kadane 算法的实现，该问题的 2D 解决方案（最大子矩形）已知为 O(n^3)（我再次确定还有其他算法，但我以前使用过这个算法）。

虽然我们知道 Theta(n^3) 可以找到二维解，但没有人能够证明 n^3 是否是下界。对于许多算法来说，当增加维度时，算法的下限就会增加一个常数值。对于这个特定的问题，复杂性不会线性增加，因此没有已知的解决方案适用于任何给定的维度，因此问题仍然悬而未决。

参考类似的情况：我们知道2个矩阵可以在n^3次内相乘。我相信还有一种算法可以在 n^2.8 中做到这一点。然而，没有数学表明我们不能让它低于 n^2.8，所以它仍然是一个“开放”算法。

Answer 2

   // 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

Answer 3

仅供参考，新版的书有一个答案，但它很模糊，我不知道它会带来什么。

无论如何，我会使用分而治之+动态规划来解决这个问题。我们将 MaxSum(x, y) 定义为以 NXN 数组左上角为界的矩形内任何子数组的最大总和，高度为 y，宽度为 x。 （因此问题的答案将在 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) 是包含 Array[x, y-1] 中的 # 的任何子数组的最大和。
同样，MaxEnding(x-1, y) 是 Array[x-1, y] 中包含 # 的任何子数组的最大和。
MaxEndingXStart(x, y-1) 是子数组的起始 x 坐标，该子数组具有包含 Array[x, y-1] 中的 # 的任何子数组的最大总和。
MaxEndingYStart (x-1, y) 是具有 Array[x-1, y] 中包含 # 的任何子数组的最大总和的子数组的起始 y 坐标。

下面#4 和#5 中的 2 个总和可以通过在遍历每一列时保留特定行中遇到的所有元素的总和来轻松计算，然后减去 2 个总和以获得特定部分的总和。

要实现这一点，您需要采用自下而上的方法，因为您需要计算 Max(x, y-1)、Max(x-1, y)、MaxEnding(x, y-1) 和 MaxEnding( x-1, y).. 因此您可以在计算 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
   }
}