查找矩阵中的最大总和子=矩形

Question

可能重复：
Getting the submatrix with maximum sum?

鉴于正和负整数的2维阵列，找到子矩形与最大的总和。矩形的总和是该矩形中所有元素的总和。在这个问题中，总和最大的子矩形被称为最大子矩形。子矩形是位于整个数组内的任何连续的大小为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）。

Answer 1

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

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

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

注意，你不需要一个向量来解决这个问题，两个变量就足够了。更多here。

现在，对于您的矩阵案例，计算Sum[i][j] = sum of the first i elements of column j。

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