查找矩阵内的最大和子=矩形[重复]

可能的重复：
获取总和最大的子矩阵？ https://stackoverflow.com/questions/2643908/getting-the-submatrix-with-maximum-sum

给定一个正整数和负整数的二维数组，找到总和最大的子矩形。矩形的总和是该矩形中所有元素的总和。在这个问题中，具有最大和的子矩形被称为最大子矩形。子矩形是位于整个数组内的任何大小为 1*1 或更大的连续子数组。例如，数组的最大子矩形：

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

位于左下角：

 9  2
-4  1
-1  8

总和为 15。

因此，给定一个矩形，找到最大子矩形之和（上例中为 15）的有效算法是什么。

你可以解决它O(numCols*numLines^2)。在 1d 中考虑同样的问题：

给定一个包含 n 个元素的向量，找到最大和连续子序列。

Let S[i] = maximum sum contiguous subsequence that ends with element i。我们有S[1] = array[1] and S[i > 1] = max(S[i - 1] + array[i], array[i]).

请注意，您不需要向量来解决此问题，两个变量就足够了。更多的here http://en.wikipedia.org/wiki/Maximum_subarray_problem.

现在，对于您的矩阵情况，计算Sum[i][j] = sum of the first i elements of column j.

现在，对于矩阵中每个可能的行对，将一维算法应用于由当前对的行之间的元素组成的“向量”。