Largest Sub-Matrix Sum

update Mar 15, 2018 15:56

Given a matrix that contains integers, find the submatrix with the largest sum.

Return the sum of the submatrix.

Assumptions:

The given matrix is not null and has size of M * N, where M >= 1 and N >= 1

Examples

{ {1, -2, -1, 4},

  {1, -1,  1, 1},

  {0, -1, -1, 1},

  {0,  0,  1, 1} }

the largest submatrix sum is (-1) + 4 + 1 + 1 + (-1) + 1 + 1 + 1 = 7.

Basic Idea:

这道题目就是要求一个矩阵中所有子矩阵中元素的最大和。

Naive Solution, brute force O(n^6):
如果不用任何技巧，求解这道题我们需要 O(N^6) (N 为边长)。因为需要四重 for 循环考虑 O(N^4) 个所有的submatrix，对于每个苏北matrix，又需要 O(N^2) 的时间求和，一共 O(N^6);
使用一维 prefix sum 数组优化 O(n^5)：
如果我们为每行建一个 prefix sum 数组，我们就可以用 O(N) 的时间求得任意一个 submatrix 的所有元素之和，如此一来时间可以优化为 O(N^5)；
使用二维 prefix sum 数组优化 O(n^4)：
试想如果有一个 2D prefix sum matrix : sums = int[][]，满足 sums[i][j] = sum{matrix 从[0,0] 到 [i,j] 的子矩阵}，则我们可以用 O(1) 的时间求得任意 submatrix 的和。而我们可以用 O(N^2) 的时间来求得sums 数组，如此一来，就将时间复杂度优化为 O(N^4) 如下图所示（但要注意edge case，图中没有考虑）：

（Code 见后面）

依然用一维 prefix sum 数组优化，结合 Kadane 求 max subarray sum 的算法 O(n^3):
与之前的几种方法不同，这次不再遍历每一个 submatrix，而是枚举所有的左右边界对，在每一对左右边界之间，求不同上下边界组成的 submatrix 的最大和，全局最大就是解。
具体地，我们可以先用 O(N^2) 的时间求所有 row 的 prefix sum 数组，如此一来，对于任意给定左右边界的某一行，我们可以用 O(1) 时间求和。那么，我们可以把任意左右边界之间的部分视为一个竖着的一维数组，其中的值就是某一行的和。于是，我们就可以使用 Kadane 算法求它的 max subarray sum，该过程耗时 O(N)，而因为共有 O(N^2) 个左右边界组合，一共要进行该过程 O(N^2) 次，所以总时间复杂度为 O(N^3)。

Java Code:

O(n^4) 解法，2D prefix sum：

public class Solution {
  public int largest(int[][] matrix) {
    int R = matrix.length, C = matrix[0].length;

    // 先获取 2D prefix sum, sums[i][j] 表示从 [0,0] 到 [i,j] submatrix 的和
    int[][] sums = new int[R][C];
    for (int r = 0; r < R; ++r) {
      for (int c = 0; c < C; ++c) {
        if (c == 0) {
          if (r == 0) { // 左上角
            sums[r][c] = matrix[r][c];
          } else { // 第一行
            sums[r][c] = matrix[r][c] + sums[r - 1][c];
          }
        } else {
          if (r == 0) { // 第一列
            sums[r][c] = matrix[r][c] + sums[r][c - 1];
          } else { // 右下方普通部分
            sums[r][c] = matrix[r][c] + sums[r][c - 1] - sums[r - 1][c - 1] + sums[r - 1][c];
          }
        }
      }
    }

    // 四重 for loop 遍历所有 submatrix
    int globalMaxSum = Integer.MIN_VALUE;
    for (int r = 0; r < R; ++r) {
      for (int c = 0; c < C; ++c) {
        // 对每个 upper left corner point, 循环遍历其开始的submatrix
        for (int i = r; i < R; ++i) {
          for (int j = c; j < C; ++j) {
            int currMatrixSum = sums[i][j];
            if (r > 0) currMatrixSum -= sums[r - 1][j];
            if (c > 0) currMatrixSum -= sums[i][c - 1];
            if (r > 0 && c > 0) currMatrixSum += sums[r - 1][c - 1];

            globalMaxSum = Math.max(globalMaxSum, currMatrixSum);
          }
        }
      }
    }
    return globalMaxSum;
  }
}

O(n^3) 解法，prefix sum + Kadane 算法：

public class Solution {
  public int largest(int[][] matrix) {
    int R = matrix.length, C = matrix[0].length;

    // 先求每行的 prefix sum
    int[][] sums = new int[R][C];
    for (int r = 0; r < R; ++r) {
      for (int c = 0; c < C; ++c) {
        if (c == 0) {
          sums[r][c] = matrix[r][c];
        } else {
          sums[r][c] = matrix[r][c] + sums[r][c - 1];
        }
      }
    }

    // 遍历每一对左右边界，在边界内考虑不同上下边界求最大和submatrix，Kadane 算法
    int globalMaxSum = Integer.MIN_VALUE;
    for (int left = 0; left < C; ++left) {
      for (int right = left; right < C; ++right) {
        int currSum = 0; // 当前左右边界间，某上下边界决定的submatrix的sum
        for (int r = 0; r < R; ++r) {
          int currRowSum = sums[r][right] - sums[r][left] + matrix[r][left];
          if (currSum < 0) {
            currSum = currRowSum;
          } else {
            currSum += currRowSum;
          }
          globalMaxSum = Math.max(globalMaxSum, currSum);
        }
      }
    }
    return globalMaxSum;
  }
}

PreviousLongest Cross of 1's NextMax Sum of Rectangle No Larger Than K (Hard)