可能重复：   获取最大金额的子矩阵？

给定一个2维的正和负整数数组，找到子矩形具有最大总和。一个矩形的总和是在该矩形的所有元素的总和。在此问题的子矩形具有最大总和被称为最大的子矩形。一个子矩形是任何连续子阵列尺寸1 * 1或更高位于整个阵列内。作为一个例子，该阵列的最大子矩形：

Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. A sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. As an example, the maximal sub-rectangle of the array:

 0 -2 -7  0
 9  2 -6  2
-4  1 -4  1
-1  8  0 -2

在左下方的角落：

is in the lower-left-hand corner:

 9  2
-4  1
-1  8

和具有15的总和

于是给定的矩形，这将是一个有效的算法找到最大的子矩形的（在上述实施例15）的总和。

So given a rectangle, what will be an efficient algorithm to find the sum of the maximal sub-rectangle (15 in the above example).

推荐答案

您可以解决它在 0（数numCols * numLines ^ 2）。考虑1D同样的问题：

You can solve it in O(numCols*numLines^2). Consider the same problem in 1d:

由于n个元素的载体，找到最大和的连续子序列。

Given a vector of n elements, find the maximum-sum contiguous subsequence.

让 S [I] =最大和连续子与元素结束我。我们有 S [1] =阵列[1] 和 S [I＆GT; 1] = MAX（S [我 - 1] +阵列[I]，数组[我]）。

请注意，你并不需要一个载体来解决这个问题，两个变量是不够的。这里更多。

Notice that you don't need a vector to solve this, two variables are enough. More here.

现在，您的矩阵的情况下，计算总和[I] [J] = j列的第i个元素的和。

Now, for your matrix case, compute Sum[i][j] = sum of the first i elements of column j.

现在，对于每个可能的对的行中的矩阵，应用1d的算法的载体从当前对的排之间的元件制成。

Now, for each possible pair of rows in your matrix, apply the 1d algorithm to the "vector" made from the elements between the rows of your current pair.