查找矩陣中的最大總和子=矩形

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算法應用到由當前對的行之間的元素構成的「向量」。