前言

给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。

返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。

注意：本题相对书上原题稍作改动

示例：

输入：
[
[-1,0],
[0,-1]
]
输出：[0,1,0,1]
解释：输入中标粗的元素即为输出所表示的矩阵

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/max-submatrix-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、大流程

矩形必须包含第0行数据,且只包含第0行的情况下,最大累加和是多少?
矩形必须包含0,1两行数据,且只包含0,1两行的情况下,最大累加和是多少?
矩形必须包含0,1,2三行数据,且只包含0,1,2三行的情况下,最大累加和是多少?
矩形必须包含0,1,2,3四行数据,且只包含0,1,2,3四行的情况下,最大累加和是多少?
然后1行~1行
1行~2行
1行~3行
1行~4行
然后2行~2行
2行~3行
2行~4行
然后3行~3行
然后4行~4行
如果我们能够每一个都求出来,答案一定在其中。

二、压缩数组技巧

矩形必须包含0,1两行数据,且只包含0,1两行的情况下,最大累加和是多少?
两行上下数据压在一起,形成一个新数组对这个数组求最大累加和就代表必须包含0,1两行数据,且只包含01两行数据画框的最好答案是啥。

    public static int maxSum(int[][] m) {
        if (m == null || m.length == 0 || m[0].length == 0) {
            return 0;
        }
        // O(N^2 * M)
        int N = m.length;
        int M = m[0].length;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            // i~j
            int[] s = new int[M];
            for (int j = i; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    s[k] += m[j][k];
                }
                max = Math.max(max, maxSubArray(s));
            }
        }
        return max;
    }
    
    public static int maxSubArray(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int cur = 0;
        for (int i = 0; i < arr.length; i++) {
            cur += arr[i];
            max = Math.max(max, cur);
            cur = cur < 0 ? 0 : cur;
        }
        return max;
    }

求坐标

回到原问题,我们只需在max更新时记录坐标即可

class Solution {
    public int[] getMaxMatrix(int[][] matrix) {
        int n=matrix.length;
        int m=matrix[0].length;
        int max=Integer.MIN_VALUE;
        int cur=0;
        int a=0;
        int b=0;
        int c=0;
        int d=0;
        //0-0,0-1...1-1,1-2...m-m
        for(int i=0;i<n;i++){
            int[] s=new int[m];
            for(int j=i;j<n;j++){
                cur=0;
                int begin=0;
                for(int k=0;k<m;k++){
                    s[k]+=matrix[j][k];
                    cur+=s[k];
                    if(max<cur){
                        max=cur;
                        a=i;
                        b=begin;
                        c=j;
                        d=k;
                    }
                    if(cur<0){
                        cur=0;
                        begin=k+1;
                    }
                }
            }
        }
        return new int[]{a,b,c,d};
    }
}