题目链接

LeetCode

题目描述

给定一个正整数、负整数和 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

    解题思路

    方法一：变形动态规划

上来那么一个三重循环的代码看得懂就奇怪了，所以我们从头说起

53.最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

这是一个简单的dp问题

  1. 状态定义：dp[i]为以nums[i]结尾的最大子序和
  2. 状态转移方程：对于nums[i]有两种情况:一种是和前一个位置的子序列连着dp[i]=dp[i-1]+nums[i]

第二种是以自己独立门户，从自己开始dp[i]=nums[i]
取其中最大值,可得状态转移方程为dp[i]=max( dp[i-1] + nums[i] , nums[i] )

  1. basecase:dp[0]=nums[0]很好理解 ```java class Solution { public: int maxSubArray(vector& nums) {
    1.  vector<int> dp(nums.size());
    2.  dp[0]=nums[0];
    3.  int ans = dp[0];
    4.  for(int i=1 ; i < nums.size() ; i++ ){
    5.      dp[i]=max(dp[i-1]+nums[i],nums[i]);
    6.      ans = max(dp[i],ans);
    7.  }
    8.  return ans;
    }

};

<br />我们观察这段代码会发现，dp[i]只与dp[i-1]和nums[i]有关，所有我们可以将空间复杂度降到O(1)<br />同时对于dp[i]=max(dp[i-1]+nums[i],nums[i]),两种情况都加了nums[i]，只是前面多加了dp[i-1]，所有很容易推出，当dp[i-1]<0时，后者大，反之前者大

这次我们变换原题的问题，如果要你返回最大子序和的起始和终止坐标呢？<br />很容易实现，我们在状态转换的时候记录一下就可以了

所有我们可以得到改进后的代码
```java
class Solution {
public:
    vector<int> maxSubArray(vector<int>& nums) {
        int maxsum=INT_MIN;
        int dp_i = nums[0];
        vector<int> ans(2);//用来记录答案
        int begin = 0;

        for(int i=1 ; i < nums.size() ; i++ ){
            if( dp_i > 0 ){    //dp[i-1] > 0 时
                dp_i+=nums[i];
            }
            else{              //dp[i-1]<0时
                dp_i=nums[i];
                begin = i;     //当nums[i]自立门户时候，我们记录下子序列的起始位置
            }
            if(dp_i > maxsum){//更新答案
                maxsum = dp_i;
                ans[0] = begin;//记录下起始和终止位置
                ans[1] = i;
            }  
        }
        return ans;
    }

};


有了上面的铺垫，我们回过头再回到我们原来的问题

面试题 17.24. 最大子矩阵

给定一个正整数和负整数组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。

问题从一维变成了二维，但实质是一样的，同样是再求最大子序和，我们需要将二维转化为一维，对于矩阵的每一列，我们将其加在一起，成为了一维上的一个数，二维矩阵的和转化为了一维数组的和

这里借用b站up zjutsunny老师的ppt
面试题 17.24. 最大子矩阵 - 图1
这样我们就将二维问题转化为了一维问题，现在另一个问题就是怎么把所有情况都遍历到呢？

我们以第i行为第一行，向下延申，设最后一行为第j行，我们就i在这么一个范围内，将二维问题转化为一维问题，再求解最大子序列和
面试题 17.24. 最大子矩阵 - 图2
我们将当前i~j行组成的矩阵的每一列的和存放在数组b中，其余的工作就是在求最大子序列和，并且保存其左上角和右下角。

class Solution {
    public int[] getMaxMatrix(int[][] matrix) {
        int[] ans = new int[4];
        int N = matrix.length;
        int M = matrix[0].length;
        int[] b = new int[M];
        int dp = 0;
        int maxSum = Integer.MIN_VALUE;
        int bestr1 = 0;
        int bestc1 = 0;
        // i 代表开始的行
        for(int i = 0; i < N; ++i){
            Arrays.fill(b, 0);
            // j 表示结束的行
            for(int j = i; j < N; ++i){
                dp = 0;
                // k 表示列
                for(int k = 0; k < M; ++k){
                    // b[k] 代表当前子矩阵到 j 行 k 列的大小
                    b[k] += matrix[j][k]; 
                    // dp 算法 当前 dp 代表上一时刻的 dp值
                    // 如果上一个时刻大于 0 ，则可以继续增大，加上当前值
                    if(dp > 0){
                        dp += b[k];
                    // 否则 dp 重新开始计算，子矩阵也要从 第 i 行 第 k 列开始
                    }else{
                        dp = b[k];
                        bestr1 = i;
                        bestc1 = k;
                    }
                    // 如果当前结果大于之前的最大值 则更新最大值并记录结果
                    if(dp > maxSum){
                        maxSum = dp;
                        ans[0] = bestr1;
                        ans[1] = bestc1;
                        ans[2] = j;
                        ans[3] = k;
                    }
                }
            }
        }
        return ans;
    }
}
  • 时间复杂度 O(n^2)
  • 空间复杂度 O(n)