获得最大总和的子matrix？

input ：具有正和负元素的二维arraysNxN – matrix。

输出 ：任何大小的子matrix，其总和在所有可能的子matrix中是最大的。

要求 ：algorithm复杂度为O（N ^ 3）

历史：在algorithm学家Larry的帮助下，对Kadane的algorithm进行了修改，我设法解决了这个问题的一部分 ，这个问题只是决定了总和 – 在Java下面。
感谢Ernesto设法解决剩下的问题，即确定matrix的边界，即左下angular，右下angular（在Ruby中）。

Answer 1

关于恢复实际的子matrix，而不只是最大的总和，这是我得到的。 对不起，我没有时间把我的代码翻译成你的Java版本，所以我发布了我的Ruby代码，在关键部分有一些注释

 def max_contiguous_submatrix_n3(m) rows = m.count cols = rows ? m.first.count : 0 vps = Array.new(rows) for i in 0..rows vps[i] = Array.new(cols, 0) end for j in 0...cols vps[0][j] = m[0][j] for i in 1...rows vps[i][j] = vps[i-1][j] + m[i][j] end end max = [m[0][0],0,0,0,0] # this is the result, stores [max,top,left,bottom,right] # these arrays are used over Kandane sum = Array.new(cols) # obvious sum array used in Kandane pos = Array.new(cols) # keeps track of the beginning position for the max subseq ending in j for i in 0...rows for k in i...rows # Kandane over all columns with the i..k rows sum.fill(0) # clean both the sum and pos arrays for the upcoming kandane pos.fill(0) local_max = 0 # we keep track of the position of the max value over each Kandane's execution # notice that we do not keep track of the max value, but only its position sum[0] = vps[k][0] - (i==0 ? 0 : vps[i-1][0]) for j in 1...cols value = vps[k][j] - (i==0 ? 0 : vps[i-1][j]) if sum[j-1] > 0 sum[j] = sum[j-1] + value pos[j] = pos[j-1] else sum[j] = value pos[j] = j end if sum[j] > sum[local_max] local_max = j end end # Kandane ends here # Here's the key thing # If the max value obtained over the past kandane's execution is larger than # the current maximum, then update the max array with sum and bounds if sum[local_max] > max[0] # sum[local_max] is the new max value # the corresponding submatrix goes from rows i..k. # and from columns pos[local_max]..local_max # the array below contains [max_sum,top,left,bottom,right] max = [sum[local_max], i, pos[local_max], k, local_max] end end end return max # return the array with [max_sum,top,left,bottom,right] end 

一些说明澄清：

为了方便，我使用一个数组来存储与结果有关的所有值。 您可以使用五个独立variables：最大值，顶部，左，底部，右。 将一行分配给数组更容易，然后子例程返回包含所有所需信息的数组。

如果您将此代码复制并粘贴到支持Ruby的支持文本高亮的编辑器中，您显然会更好地理解它。 希望这可以帮助！

Answer 2

这里是解释发布的代码。 有两个关键的技巧，使其有效地工作：（一）康达的algorithm和（二）使用前缀总和。 你还需要（三）把技巧应用到matrix。

第一部分：康达的algorithm

Kandane的algorithm是一种寻找最大和的连续子序列的方法。 让我们从一个蛮力方法开始寻找最大的连续子序列，然后考虑优化它来获得Kandane的algorithm。

假设你有序列：

 -1, 2, 3, -2 

对于蛮力方法，沿着序列走，生成所有可能的子序列，如下所示。 考虑到所有可能性，我们可以开始，扩展或结束每一步的列表。

 At index 0, we consider appending the -1 -1, 2, 3, -2 ^ Possible subsequences: -1 [sum -1] At index 1, we consider appending the 2 -1, 2, 3, -2 ^ Possible subsequences: -1 (end) [sum -1] -1, 2 [sum 1] 2 [sum 2] At index 2, we consider appending the 3 -1, 2, 3, -2 ^ Possible subsequences: -1, (end) [sum -1] -1, 2 (end) [sum -1] 2 (end) [sum 2] -1, 2, 3 [sum 4] 2, 3 [sum 5] 3 [sum 3] At index 3, we consider appending the -2 -1, 2, 3, -2 ^ Possible subsequences: -1, (end) [sum -1] -1, 2 (end) [sum 1] 2 (end) [sum 2] -1, 2 3 (end) [sum 4] 2, 3 (end) [sum 5] 3, (end) [sum 3] -1, 2, 3, -2 [sum 2] 2, 3, -2 [sum 3] 3, -2 [sum 1] -2 [sum -2] 

对于这个暴力方法，我们最后select最好的数目， (2, 3) ，这就是答案。 但是为了使这个效率更高，考虑一下你实际上不需要保留每一个列表。 在没有结束的列表中，你只需要保留最好的列表，其他的不能做得更好。 在已经结束的列表之外，你只需要保持最好的列表，只有它比没有结束的列表更好。

所以，只需要一个位置数组和一个和数组就能跟踪你所需要的东西。 位置数组定义如下： position[r] = s跟踪以r结尾的列表，并以s开始。 并且， sum[r]给出了在index r处结束的子序列的和。 这是优化的方法是Kandane的algorithm。

再次运行示例，以这种方式跟踪我们的进度：

 At index 0, we consider appending the -1 -1, 2, 3, -2 ^ We start a new subsequence for the first element. position[0] = 0 sum[0] = -1 At index 1, we consider appending the 2 -1, 2, 3, -2 ^ We choose to start a new subsequence because that gives a higher sum than extending. position[0] = 0 sum[0] = -1 position[1] = 1 sum[1] = 2 At index 2, we consider appending the 3 -1, 2, 3, -2 ^ We choose to extend a subsequence because that gives a higher sum than starting a new one. position[0] = 0 sum[0] = -1 position[1] = 1 sum[1] = 2 position[2] = 1 sum[2] = 5 Again, we choose to extend because that gives a higher sum that starting a new one. -1, 2, 3, -2 ^ position[0] = 0 sum[0] = -1 position[1] = 1 sum[1] = 2 position[2] = 1 sum[2] = 5 positions[3] = 3 sum[3] = 3 

再次，最好的总和是5，列表是从索引1到索引2，这是（2,3）。

第二部分：前缀总和

我们想要有一种方法来计算任何起点到任何终点的总和。 我想在O（1）时间内计算这个总和，而不是仅仅加上，这需要O（m）时间，其中m是总和中元素的数量。 有了一些预先计算，这可以达到目的。 就是这样。 假设你有一个matrix：

 adg behcfi 

你可以预先计算这个matrix：

 adg a+b d+e g+h a+b+c d+e+f g+h+i 

一旦完成，您可以通过减去两个值从列中的任何开始点到结束点的任何列获得总和。

第三部分：把技巧一起find最大的子matrix

假设您知道最大子matrix的顶部和底部行。 你可以这样做：

1. 忽略顶行上面的行，忽略底行下面的行。
2. 用什么matrix保留，考虑每个列的使用总和形成一个序列（有点像表示多行的行）。 （你可以用前缀和方法快速计算这个序列的任何元素。）
3. 用Kandane的方法来找出这个序列中最好的子序列。 你得到的索引将会告诉你最好的子matrix的左右位置。

现在怎么样算出顶部和底部的行？ 只要尝试一切可能性。 尝试在任何可能的地方放置顶部，并将底部放在任何位置，然后运行之前描述的基于甘丹碱的过程，以实现各种可能性。 当你find一个最大值，你跟踪的顶部和底部的位置。

查找行和列需要O（M ^ 2），其中M是行数。 查找列需要O（N）时间，其中N是列数。 所以总时间是O（M ^ 2 * N）。 而且，如果M = N，则所需的时间是O（N ^ 3）。

Answer 3

已经有很多答案了，但是这是我写的另一个Java实现。 它比较了三种解决scheme

1. 天真（蛮力） – O（n ^ 6）时间
2. 明显的DP解决scheme – O（n ^ 4）时间和O（n ^ 3）空间
3. 基于Kadanealgorithm的更巧妙的DP解决scheme – O（n ^ 3）时间和O（n ^ 2）空间

对于n = 10到n = 70，以10为增量进行样品运行，并比较运行时间和空间要求。

码：

 public class MaxSubarray2D { static int LENGTH; final static int MAX_VAL = 10; public static void main(String[] args) { for (int i = 10; i <= 70; i += 10) { LENGTH = i; int[][] a = new int[LENGTH][LENGTH]; for (int row = 0; row < LENGTH; row++) { for (int col = 0; col < LENGTH; col++) { a[row][col] = (int) (Math.random() * (MAX_VAL + 1)); if (Math.random() > 0.5D) { a[row][col] = -a[row][col]; } //System.out.printf("%4d", a[row][col]); } //System.out.println(); } System.out.println("N = " + LENGTH); System.out.println("-------"); long start, end; start = System.currentTimeMillis(); naiveSolution(a); end = System.currentTimeMillis(); System.out.println(" run time: " + (end - start) + " ms no auxiliary space requirements"); start = System.currentTimeMillis(); dynamicProgammingSolution(a); end = System.currentTimeMillis(); System.out.println(" run time: " + (end - start) + " ms requires auxiliary space for " + ((int) Math.pow(LENGTH, 4)) + " integers"); start = System.currentTimeMillis(); kadane2D(a); end = System.currentTimeMillis(); System.out.println(" run time: " + (end - start) + " ms requires auxiliary space for " + + ((int) Math.pow(LENGTH, 2)) + " integers"); System.out.println(); System.out.println(); } } // O(N^2) !!! public static void kadane2D(int[][] a) { int[][] s = new int[LENGTH + 1][LENGTH]; // [ending row][sum from row zero to ending row] (rows 1-indexed!) for (int r = 0; r < LENGTH + 1; r++) { for (int c = 0; c < LENGTH; c++) { s[r][c] = 0; } } for (int r = 1; r < LENGTH + 1; r++) { for (int c = 0; c < LENGTH; c++) { s[r][c] = s[r - 1][c] + a[r - 1][c]; } } int maxSum = Integer.MIN_VALUE; int maxRowStart = -1; int maxColStart = -1; int maxRowEnd = -1; int maxColEnd = -1; for (int r1 = 1; r1 < LENGTH + 1; r1++) { // rows 1-indexed! for (int r2 = r1; r2 < LENGTH + 1; r2++) { // rows 1-indexed! int[] s1 = new int[LENGTH]; for (int c = 0; c < LENGTH; c++) { s1[c] = s[r2][c] - s[r1 - 1][c]; } int max = 0; int c1 = 0; for (int c = 0; c < LENGTH; c++) { max = s1[c] + max; if (max <= 0) { max = 0; c1 = c + 1; } if (max > maxSum) { maxSum = max; maxRowStart = r1 - 1; maxColStart = c1; maxRowEnd = r2 - 1; maxColEnd = c; } } } } System.out.print("KADANE SOLUTION | Max sum: " + maxSum); System.out.print(" Start: (" + maxRowStart + ", " + maxColStart + ") End: (" + maxRowEnd + ", " + maxColEnd + ")"); } // O(N^4) !!! public static void dynamicProgammingSolution(int[][] a) { int[][][][] dynTable = new int[LENGTH][LENGTH][LENGTH + 1][LENGTH + 1]; // [row][col][height][width] int maxSum = Integer.MIN_VALUE; int maxRowStart = -1; int maxColStart = -1; int maxRowEnd = -1; int maxColEnd = -1; for (int r = 0; r < LENGTH; r++) { for (int c = 0; c < LENGTH; c++) { for (int h = 0; h < LENGTH + 1; h++) { for (int w = 0; w < LENGTH + 1; w++) { dynTable[r][c][h][w] = 0; } } } } for (int r = 0; r < LENGTH; r++) { for (int c = 0; c < LENGTH; c++) { for (int h = 1; h <= LENGTH - r; h++) { int rowTotal = 0; for (int w = 1; w <= LENGTH - c; w++) { rowTotal += a[r + h - 1][c + w - 1]; dynTable[r][c][h][w] = rowTotal + dynTable[r][c][h - 1][w]; } } } } for (int r = 0; r < LENGTH; r++) { for (int c = 0; c < LENGTH; c++) { for (int h = 0; h < LENGTH + 1; h++) { for (int w = 0; w < LENGTH + 1; w++) { if (dynTable[r][c][h][w] > maxSum) { maxSum = dynTable[r][c][h][w]; maxRowStart = r; maxColStart = c; maxRowEnd = r + h - 1; maxColEnd = c + w - 1; } } } } } System.out.print(" DP SOLUTION | Max sum: " + maxSum); System.out.print(" Start: (" + maxRowStart + ", " + maxColStart + ") End: (" + maxRowEnd + ", " + maxColEnd + ")"); } // O(N^6) !!! public static void naiveSolution(int[][] a) { int maxSum = Integer.MIN_VALUE; int maxRowStart = -1; int maxColStart = -1; int maxRowEnd = -1; int maxColEnd = -1; for (int rowStart = 0; rowStart < LENGTH; rowStart++) { for (int colStart = 0; colStart < LENGTH; colStart++) { for (int rowEnd = 0; rowEnd < LENGTH; rowEnd++) { for (int colEnd = 0; colEnd < LENGTH; colEnd++) { int sum = 0; for (int row = rowStart; row <= rowEnd; row++) { for (int col = colStart; col <= colEnd; col++) { sum += a[row][col]; } } if (sum > maxSum) { maxSum = sum; maxRowStart = rowStart; maxColStart = colStart; maxRowEnd = rowEnd; maxColEnd = colEnd; } } } } } System.out.print(" NAIVE SOLUTION | Max sum: " + maxSum); System.out.print(" Start: (" + maxRowStart + ", " + maxColStart + ") End: (" + maxRowEnd + ", " + maxColEnd + ")"); } } 

Answer 4

下面是Ernesto实现的Java版本，进行了一些修改：

 public int[][] findMaximumSubMatrix(int[][] matrix){ int dim = matrix.length; //computing the vertical prefix sum for columns int[][] ps = new int[dim][dim]; for (int i = 0; i < dim; i++) { for (int j = 0; j < dim; j++) { if (j == 0) { ps[j][i] = matrix[j][i]; } else { ps[j][i] = matrix[j][i] + ps[j - 1][i]; } } } int maxSum = matrix[0][0]; int top = 0, left = 0, bottom = 0, right = 0; //Auxiliary variables int[] sum = new int[dim]; int[] pos = new int[dim]; int localMax; for (int i = 0; i < dim; i++) { for (int k = i; k < dim; k++) { // Kandane over all columns with the i..k rows reset(sum); reset(pos); localMax = 0; //we keep track of the position of the max value over each Kandane's execution // notice that we do not keep track of the max value, but only its position sum[0] = ps[k][0] - (i==0 ? 0 : ps[i-1][0]); for (int j = 1; j < dim; j++) { if (sum[j-1] > 0){ sum[j] = sum[j-1] + ps[k][j] - (i==0 ? 0 : ps[i-1][j]); pos[j] = pos[j-1]; }else{ sum[j] = ps[k][j] - (i==0 ? 0 : ps[i-1][j]); pos[j] = j; } if (sum[j] > sum[localMax]){ localMax = j; } }//Kandane ends here if (sum[localMax] > maxSum){ /* sum[localMax] is the new max value the corresponding submatrix goes from rows i..k. and from columns pos[localMax]..localMax */ maxSum = sum[localMax]; top = i; left = pos[localMax]; bottom = k; right = localMax; } } } System.out.println("Max SubMatrix determinant = " + maxSum); //composing the required matrix int[][] output = new int[bottom - top + 1][right - left + 1]; for(int i = top, k = 0; i <= bottom; i++, k++){ for(int j = left, l = 0; j <= right ; j++, l++){ output[k][l] = matrix[i][j]; } } return output; } private void reset(int[] a) { for (int index = 0; index < a.length; index++) { a[index] = 0; } } 

Answer 5

在Algorithmist和Larry的帮助下以及对Kadanealgorithm的修改，这里是我的解决scheme：

 int dim = matrix.length; //computing the vertical prefix sum for columns int[][] ps = new int[dim][dim]; for (int i = 0; i < dim; i++) { for (int j = 0; j < dim; j++) { if (j == 0) { ps[j][i] = matrix[j][i]; } else { ps[j][i] = matrix[j][i] + ps[j - 1][i]; } } } int maxSoFar = 0; int min , subMatrix; //iterate over the possible combinations applying Kadane's Alg. for (int i = 0; i < dim; i++) { for (int j = i; j < dim; j++) { min = 0; subMatrix = 0; for (int k = 0; k < dim; k++) { if (i == 0) { subMatrix += ps[j][k]; } else { subMatrix += ps[j][k] - ps[i - 1 ][k]; } if(subMatrix < min){ min = subMatrix; } if((subMatrix - min) > maxSoFar){ maxSoFar = subMatrix - min; } } } } 

剩下的唯一东西是确定子matrix元素，即：子matrix的左上angular和右下angular。 任何人的build议？

Answer 6

我打算在这里发表一个答案，并可以添加实际的c ++代码，如果这是因为我最近通过这个请求。 一些可以在O（N ^ 2）中解决这个问题的分而治之的传言在外面，但我还没有看到任何代码可以支持。 根据我的经验，以下是我发现的。

  O(i^3j^3) -- naive brute force method o(i^2j^2) -- dynamic programming with memoization O(i^2j) -- using max contiguous sub sequence for an array if ( i == j ) O(n^6) -- naive O(n^4) -- dynamic programming O(n^3) -- max contiguous sub sequence 

Answer 7

看一看JAMA包装; 我相信这会让你的生活更轻松。

Answer 8

这是C＃解决scheme。 参考： http : //www.algorithmist.com/index.php/UVa_108

 public static MaxSumMatrix FindMaxSumSubmatrix(int[,] inMtrx) { MaxSumMatrix maxSumMtrx = new MaxSumMatrix(); // Step 1. Create SumMatrix - do the cumulative columnar summation // S[i,j] = S[i-1,j]+ inMtrx[i-1,j]; int m = inMtrx.GetUpperBound(0) + 2; int n = inMtrx.GetUpperBound(1)+1; int[,] sumMatrix = new int[m, n]; for (int i = 1; i < m; i++) { for (int j = 0; j < n; j++) { sumMatrix[i, j] = sumMatrix[i - 1, j] + inMtrx[i - 1, j]; } } PrintMatrix(sumMatrix); // Step 2. Create rowSpans starting each rowIdx. For these row spans, create a 1-D array r_ij for (int x = 0; x < n; x++) { for (int y = x; y < n; y++) { int[] r_ij = new int[n]; for (int k = 0; k < n; k++) { r_ij[k] = sumMatrix[y + 1,k] - sumMatrix[x, k]; } // Step 3. Find MaxSubarray of this r_ij. If the sum is greater than the last recorded sum => // capture Sum, colStartIdx, ColEndIdx. // capture current x as rowTopIdx, y as rowBottomIdx. MaxSum currMaxSum = KadanesAlgo.FindMaxSumSubarray(r_ij); if (currMaxSum.maxSum > maxSumMtrx.sum) { maxSumMtrx.sum = currMaxSum.maxSum; maxSumMtrx.colStart = currMaxSum.maxStartIdx; maxSumMtrx.colEnd = currMaxSum.maxEndIdx; maxSumMtrx.rowStart = x; maxSumMtrx.rowEnd = y; } } } return maxSumMtrx; } public static void PrintMatrix(int[,] matrix) { int endRow = matrix.GetUpperBound(0); int endCol = matrix.GetUpperBound(1); PrintMatrix(matrix, 0, endRow, 0, endCol); } public static void PrintMatrix(int[,] matrix, int startRow, int endRow, int startCol, int endCol) { StringBuilder sb = new StringBuilder(); for (int i = startRow; i <= endRow; i++) { sb.Append(Environment.NewLine); for (int j = startCol; j <= endCol; j++) { sb.Append(string.Format("{0} ", matrix[i,j])); } } Console.WriteLine(sb.ToString()); } // Given an NxN matrix of positive and negative integers, write code to find the sub-matrix with the largest possible sum public static MaxSum FindMaxSumSubarray(int[] inArr) { int currMax = 0; int currStartIndex = 0; // initialize maxSum to -infinity, maxStart and maxEnd idx to 0. MaxSum mx = new MaxSum(int.MinValue, 0, 0); // travers through the array for (int currEndIndex = 0; currEndIndex < inArr.Length; currEndIndex++) { // add element value to the current max. currMax += inArr[currEndIndex]; // if current max is more that the last maxSum calculated, set the maxSum and its idx if (currMax > mx.maxSum) { mx.maxSum = currMax; mx.maxStartIdx = currStartIndex; mx.maxEndIdx = currEndIndex; } if (currMax < 0) // if currMax is -ve, change it back to 0 { currMax = 0; currStartIndex = currEndIndex + 1; } } return mx; } struct MaxSum { public int maxSum; public int maxStartIdx; public int maxEndIdx; public MaxSum(int mxSum, int mxStart, int mxEnd) { this.maxSum = mxSum; this.maxStartIdx = mxStart; this.maxEndIdx = mxEnd; } } class MaxSumMatrix { public int sum = int.MinValue; public int rowStart = -1; public int rowEnd = -1; public int colStart = -1; public int colEnd = -1; } 

Answer 9

这是我的2D Kadanealgorithm的实现。 我认为这是更清楚的。 这个概念基于kadanealgorithm。 主要部分（在代码的底部）的第一个和第二个循环是挑选行的每一个组合，第三个循环是使用一维kadanealgorithm由每个列的总和（可以在常量时间计算，因为通过从两个拾取（从combintation）行中减去值来预处理matrix）。 这里是代码：

  int [][] m = { {1,-5,-5}, {1,3,-5}, {1,3,-5} }; int N = m.length; // summing columns to be able to count sum between two rows in some column in const time for (int i=0; i<N; ++i) m[0][i] = m[0][i]; for (int j=1; j<N; ++j) for (int i=0; i<N; ++i) m[j][i] = m[j][i] + m[j-1][i]; int total_max = 0, sum; for (int i=0; i<N; ++i) { for (int k=i; k<N; ++k) { //for each combination of rows sum = 0; for (int j=0; j<N; j++) { //kadane algorithm for every column sum += i==0 ? m[k][j] : m[k][j] - m[i-1][j]; //for first upper row is exception total_max = Math.max(sum, total_max); } } } System.out.println(total_max); 

Answer 10

这是我的解决scheme。 它是O（n ^ 3）和O（n ^ 2）空间。 https://gist.github.com/toliuweijing/6097144

 // 0th O(n) on all candidate bottoms @B. // 1th O(n) on candidate tops @T. // 2th O(n) on finding the maximum @left/@right match. int maxRect(vector<vector<int> >& mat) { int n = mat.size(); vector<vector<int> >& colSum = mat; for (int i = 1 ; i < n ; ++i) for (int j = 0 ; j < n ; ++j) colSum[i][j] += colSum[i-1][j]; int optrect = 0; for (int b = 0 ; b < n ; ++b) { for (int t = 0 ; t <= b ; ++t) { int minLeft = 0; int rowSum[n]; for (int i = 0 ; i < n ; ++i) { int col = t == 0 ? colSum[b][i] : colSum[b][i] - colSum[t-1][i]; rowSum[i] = i == 0? col : col + rowSum[i-1]; optrect = max(optrect, rowSum[i] - minLeft); minLeft = min(minLeft, rowSum[i]); } } } return optrect; } 

Answer 11

我只是parsingNxN数组，删除-ves，剩下的就是子matrix的最高和。

这个问题并没有说你必须保持原始matrix不变或命令重要。