【LeetCode: 面试题 17.24. 最大子矩阵 | 动态规划 】

题目链接

• 面试题 17.24. 最大子矩阵

⛲ 题目描述

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

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

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

示例

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

说明

1 <= matrix.length, matrix[0].length <= 200

求解思路&实现代码&运行结果

---

⚡ 动态规划

求解思路

1. 再学习这道题题目之前大家可以先去看一下另一道最大子数组和的题解再来学习这道题目就会非常容易。【LeetCode: 53. 最大子数组和 | 暴力递归=记忆化搜索=动态规划 | 分治法 】
2. 我们先来简单理解一下这道题目的意思这道题目区别于53.最大子数组和最大的不同在于53题是一维的但是这道题目是一个升级的版本是二维的但是核心的求解内思路是一样的。
3. 既让说思路是一样的那么我现在知道怎么求解一个一维数组的方法但是并不知道二维数组怎么求解这该怎么办呢我们直接将二维数组转换为一维数组进性求解即可怎么转换呢就是挨个遍历从start开始到end结束的行按照列对其进行一个压缩即可。
4. 然后我们找到最大子矩阵的和如果当前的子矩阵的和是最大的我们直接更新并且抓取矩阵的坐标最后直接返回即可。
5. 有了基本的思路接下来我们就来通过代码来实现一下。

实现代码

class Solution {
    public int[] getMaxMatrix(int[][] matrix) {
        int m=matrix.length,n=matrix[0].length;
        int r1=0,c1=0,r2=0,c2=0;
        int max=Integer.MIN_VALUE,cur=0;
        for(int i=0;i<m;i++){
            int[] temp=new int[n];
            for(int j=i;j<m;j++){
                int start=0;
                cur=0;
                for(int k=0;k<n;k++){
                    temp[k]+=matrix[j][k];
                    cur+=temp[k];
                    if(cur>max){
                        max=cur;
                        r1=i;
                        c1=start;
                        r2=j;
                        c2=k;
                    }
                    if(cur<0){
                        cur=0;
                        start=k+1;
                    }
                }
            }
        }
        return new int[]{r1,c1,r2,c2};
    }
}

运行结果

时间复杂度O(M*M*N)

空间复杂度:O(N)

共勉

最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉