给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
注意：本题相对书上原题稍作改动
示例：
输入：
[
  [-1,0],
  [0,-1]
]
输出：[0,1,0,1]
解释：输入中标粗的元素即为输出所表示的矩阵

解题思路：

试想一下如果知道二维数组的所有项的前项之和（前缀和），这样就相当于知道了所有子矩阵的和，这个时候只需要穷举所有子矩阵的和，取最大子矩阵即可得到结果。

那么如何求二维数组的前缀和呢？

可以参考这道题-二位区域和检索-矩阵不可变

对于二维数组的穷举，这里就不在赘述了。

// 固定上下
for (int top = 0; top < rows; top++) {
  for (int bottom = top; bottom < rows; bottom++) {
    // 固定左右
    for (int left = 0; left < cols; left++) {
      for (int right = left; right < cols; right++) {
        // (top, left)，(bottom, right)
        int num = sums[bottom+1][right+1] - sums[bottom+1][left] - sums[top][right+1] + sums[top][left];
        ...
      }
    }
  }
}

代码实现：

public class Solution_109 {

    public int[] getMaxMatrix(int[][] matrix) {
        int rl = matrix.length;
        int cl = matrix[0].length;

        // 前缀和
        int[][] sums = new int[rl + 1][cl + 1];
        for (int i = 0; i < rl; i++) {
            sums[i][0] = 0;
        }
        for (int i = 0; i < cl; i++) {
            sums[0][i] = 0;
        }
        for (int i = 0; i < rl; i++) {
            for (int j = 0; j < cl; j++) {
                sums[i + 1][j + 1] = sums[i + 1][j] + sums[i][j + 1] - sums[i][j] + matrix[i][j];
            }
        }

        // 穷举所有结果
        int[] res = new int[4];
        int max = Integer.MIN_VALUE;
        // 上下
        for (int top = 0; top < rl; top++) {
            for (int bottom = top; bottom < rl; bottom++) {

                // 左右
                for (int left = 0; left < cl; left++) {
                    for (int right = left; right < cl; right++) {

                        int sum = sums[bottom + 1][right + 1] - sums[top][right + 1] -
                                sums[bottom + 1][left] + sums[top][left];

                        if (max < sum) {
                            max = sum;
                            res[0] = top;
                            res[1] = left;
                            res[2] = bottom;
                            res[3] = right;
                        }

                    }
                }

            }
        }

        return res;
    }

    public static void main(String[] args) {
        Solution_109 solution_109 = new Solution_109();
        System.out.println(Arrays.toString(solution_109.getMaxMatrix(new int[][]{
                {9, -8, 1, 3, -2}, {-3, 7, 6, -2, 4}, {6, -4, -4, 8, -7}
        })));
    }
}