获得最大总和的子矩阵？

Question

输入:二维数组NxN - 矩阵 - 具有正负元素.

输出:任何大小的子矩阵,使得其总和是所有可能子矩阵中的最大值.

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

历史:在Algorithmist,Larry和Kadane算法的修改的帮助下,我设法解决了部分问题,即仅在Java中确定求和.
感谢Ernesto设法解决问题的其余部分,即确定矩阵的边界,即左上角,右下角 - 在Ruby下面.

Answer 1

以下是发布代码的说明.有效地使这项工作有两个关键技巧:(I)Kadane的算法和(II)使用前缀和.您还需要(III)将技巧应用于矩阵.

第一部分:卡丹的算法

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]给出结束于的子序列的总和index 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

完成后,您可以通过减去两个值,从列中的任何起点到终点沿着任何列运行总和.

第三部分:将技巧结合在一起以找到最大子矩阵

假设您知道max子矩阵的顶行和底行.你可以这样做:

1. 忽略顶行上方的行,忽略底行下方的行.
2. 使用什么矩阵,考虑每列的使用总和来形成一个序列(有点像一行代表多行).(您可以使用前缀sums方法快速计算此序列的任何元素.)
3. 使用Kadane的方法来计算此序列中的最佳子序列.您获得的索引将告诉您最佳子矩阵的左侧和右侧位置.

现在,实际找出顶行和底行怎么样？试试所有可能性.尝试将顶部放在任何可能的位置并将底部放在任何位置,并运行前面描述的基于Kadane的程序,以实现各种可能性.当您找到最大值时,您可以跟踪顶部和底部位置.

查找行和列需要O(M ^ 2),其中M是行数.查找列需要O(N)时间,其中N是列数.所以总时间是O(M ^ 2*N).并且,如果M = N,则所需的时间是O(N ^ 3).

Answer 2

关于恢复实际的子矩阵,而不仅仅是最大总和,这是我得到的.抱歉,我没有时间将我的代码翻译成你的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,您显然可以更好地理解它.希望这可以帮助!

Answer 3

已经有很多答案,但这是我写的另一个Java实现.它比较了3个解决方案

1. Naïve(蛮力) - O(n ^ 6)时间
2. 显而易见的DP解决方案 - O(n ^ 4)时间和O(n ^ 3)空间
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 + ")");
    }

}

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++) {
            // 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;
    }
}