在矩阵中查找最大和子sub =矩形

Question

可能重复:
获得最大总和的子矩阵？

给定正整数和负整数的二维数组,找到具有最大总和的子矩形.矩形的总和是该矩形中所有元素的总和.在这个问题中,具有最大和的子矩形被称为最大子矩形.子矩形是位于整个阵列内的任何大小为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]).

请注意,您不需要向量来解决此问题,两个变量就足够了.更多这里.

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

现在,对于矩阵中每对可能的行,将1d算法应用于由当前对的行之间的元素组成的"向量".