获取具有最大和的子矩阵？

Question

获取具有最大和的子矩阵？

algorithmdynamic-programmingmaxsubmatrix

66

输入: 一个N*N的二维数组矩阵，矩阵中包含正数和负数元素。

输出: 任意大小的子矩阵，其所有子矩阵中元素之和最大。

要求: 算法复杂度为O(N^3)

历史: 在Algorithmist Larry和Kadane算法的修改帮助下，我已经解决了部分问题，即仅确定总和 - 下面是Java代码。
感谢Ernesto解决了该问题的其余部分，即确定矩阵的边界，即左上角和右下角 - 下面是Ruby代码。

- guirgis

1

“n维度”指的是二维度。N*N，不是N的n次方。 - Kobi

这是一个动态规划问题，你可以在Algorithmist上阅读关于O(N^3)解决方案的内容。 - Larry

谢谢Larry。根据该算法，这应该是第一步： int dim = matrix.length; int[][] ps = new int[dim][dim]; for (int i = 0; i < dim; i++) { for (int j = 0; j < dim; j++) { if (j == 0) { ps[i][j] = matrix[i][j]; } else { ps[i][j] = matrix[i][j] + ps[i][j - 1]; } } } 第二步是获取n^2个组合，并对它们应用我之前发布的算法以找到最大值。所以我的问题现在是如何找到这些组合。有人能帮忙吗？ - guirgis

我的意思是每个组合都应该是一个一维数组，传递给计算最大子数组的函数，我如何从部分和矩阵中获取这些数组？ - guirgis

好的，有n^2行，这就是你的组合。如果你已经有了部分和，你可以在O(1)时间内查询下一列（在这些行内），这类似于处理传统的一维Kadane算法中的单个元素。 - Larry

显示剩余6条评论

11个回答

22

关于恢复实际子矩阵而不仅仅是最大和，这是我得到的代码。很抱歉我没有时间将我的代码翻译成你的 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 Kadane
  sum = Array.new(cols) # obvious sum array used in Kadane
  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
      # Kadane over all columns with the i..k rows
      sum.fill(0) # clean both the sum and pos arrays for the upcoming Kadane
      pos.fill(0)
      local_max = 0 # we keep track of the position of the max value over each Kadane'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
      # Kadane ends here

      # Here's the key thing
      # If the max value obtained over the past Kadane'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

一些澄清的注释：

我使用一个数组来存储与结果相关的所有值，以便于操作。你也可以使用五个独立的变量：max，top，left，bottom，right。只是将这些值在一行中分配给数组更容易，然后子例程返回具有所有必要信息的数组。

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

- Ernesto

你好Ernesto，我刚看到了你的回答，非常感谢你的努力。我很快会查看你的实现。 - guirgis

11

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

朴素（暴力）- O(n^6)时间复杂度
显而易见的DP解法 - O(n^4)时间复杂度和O(n^3)空间复杂度
基于Kadane算法的更聪明的DP解法 - 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 + ")");
    }

}

- The111

7

这是一个带有一些修改的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++) {
            // Kadane 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 Kadane'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;
                }
            }//Kadane 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;
    }
}

- guirgis

3

在算法工程师和Larry的帮助下，并使用Kadane算法的修改版本，这是我的解决方案：

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;
                }                    
            }
        }
    }

唯一剩下的就是确定子矩阵元素，即子矩阵的左上角和右下角。有什么建议吗？

- guirgis

2

只需在if语句中跟踪它。顺便说一句，最好编辑您的原始问题，而不是提交答案。 - Larry

我已经在一维问题中成功完成了这个： for (int i = 0; i < a.length; i++) { subArray += a[i]; if(subArray < min){ offset = i+1; min = subArray; }
if((subArray - min) > best){ length ++; best = subArray - min; }
} 但是在矩阵情况下遇到了一些问题。抱歉我是新手，不知道什么是best。 - guirgis

如果您存储了一个偏移变量，那么您已经知道i、j和k，因此您可以从中计算出子矩阵的角落。 - Larry

感谢Larry的帮助。我知道这就是我应该做的，但问题是我无法确定在知道“min”元素坐标的情况下偏移量将在哪里，还有如何应用长度值找到正确的角落。 - guirgis

2

这是我实现的二维Kadane算法。我认为它更加清晰易懂。该算法基于Kadane算法，主要部分的第一和第二个循环用于选择每一行的组合，第三个循环使用一维Kadane算法，通过计算每列的和（由于矩阵的预处理，可在常数时间内完成，通过从组合中选择两行并减去其值）。以下是代码：

    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);

- Sebastian Lipnicki

1

我将在此发布答案，如果需要的话，可以添加实际的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

- bjackfly

0

这是C#的解决方案。参考：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;
}

- saket

0

看一下 JAMA 包；我相信它会让你的生活更轻松。

- Anax

谢谢Anax。这是一个有用的包，我以前从未听说过，但我认为我需要使用标准API，因为这是一种算法问题。 - guirgis

-2

这是我的解决方案。时间复杂度为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;
}

- jim liu

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rick Giuly · Accepted Answer

这里是一段解释，用于说明贴出的代码。实现这个问题需要掌握两个关键技巧：(I) Kadane算法和(II)使用前缀和。你还需要将这些技巧应用到矩阵中 (III)。

第一部分：Kadane算法

Kadane算法是一种找到最大连续子序列的方法。让我们从暴力算法开始寻找最大连续子序列，然后考虑优化它以得到Kadane算法。

假设你有一个序列：

-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]

对于这种暴力方法，我们最终选择拥有最佳总和的列表(2, 3)，那就是答案。然而，为了使其更加高效，考虑到你实际上不需要保存每一个列表。在尚未结束的列表中，只需保留最好的一个，其他列表不能做得更好。对于已经结束的列表，只有当其比尚未结束的列表更好时，才需要保留最佳的一个。

因此，你可以通过只使用一个位置数组和一个求和数组来跟踪所需信息。位置数组定义如下：position[r] = s表示以r结尾且从s开始的列表。而sum[r]给出以索引r结尾的子序列的总和。这种优化方法称为Kadane算法。

再次运行示例，按照此方式跟踪进度：

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是总和中元素的数量。通过预处理，可以实现这一点。以下是如何实现的。假设你有一个矩阵：

a   d   g
b   e   h 
c   f   i

你可以预先计算这个矩阵：

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

完成这个步骤之后，你可以通过减去两个值，在任意一列中从任何起点到终点计算和。

第三部分：结合技巧寻找最大子矩阵

假设您知道最大子矩阵的顶行和底行。您可以执行以下操作：

忽略顶行以上和底行以下的行。
使用剩余矩阵的每列总和来形成一个序列（类似于表示多行的行）。（您可以使用前缀和方法快速计算此序列的任何元素。）
使用Kadane方法在此序列中查找最佳子序列。您获得的索引将告诉您最佳子矩阵的左侧和右侧位置。

那么，如何确定顶行和底行呢？尝试所有可能性。尝试将顶部放在您可以的任何位置，并将底部放在您可以的任何位置，并为每个可能性运行先前描述的Kadane基本过程。找到最大值时，记录顶部和底部位置。

找到行和列需要O(M^2)时间，其中M是行数。找到列需要O(N)时间，其中N是列数。因此总时间复杂度为O（M^2 * N）。如果M = N，则所需的时间为O（N ^ 3）。