动态规划---例题4.最大子矩阵和问题

本题与力扣面试题 17.24. 最大子矩阵相同.

一.问题描述

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

二.解题思路

如果有看过经典例题3 --- ,就会很快知道该问题的突破口.
我们知道,最大子段和是针对一维数组而言,可以找到该数组中连续子数组之和最大的那一个.而对于本题,我们需要求解最大子矩阵和,就是将一维问题转化为了二维问题.最大子矩阵和问题是最大子段和问题向二维的推广.

我们用a[1:m] [1:n]表示给定的m行n列的整数矩阵.子数组a[i1:i2] [j1:j2]表示左上角和右下角行列坐标分别为(r1, c1)和(r2, c2)的子矩阵,
其各元素之和记为:

容易看出(不太容易??):

我们只要记住,将二维数组压缩成为一维数组即可.
这正是一维情形的最大子段和问题.由此,借助最大子段和问题的动态算法MaxSum,可设计出解最大子矩阵和问题的动态规划算法getMaxMatrix如下:
通过MaxSum这个函数得到一维数组中最大连续子数组的起始左边界和右边界.

int MaxSum(vector &nums, int &left, int &right) 
{
    int n = nums.size();
    if(n==0) return {};
    int begin = 0;
    int pre = INT_MIN, maxAns = nums[0];
    for(int i=0; i 0)
        {
            pre = pre + nums[i];
        }
        else  //pre带来的是负能量,故舍弃pre.自立门户,重新给begin赋值.
        {
            begin = i;
            pre = nums[i];
        }
        if(pre > maxAns)
        {
            maxAns = pre;
            left = begin;  //记住只有满足pre>maxAns这个条件之后才能够更新left,right.不然就可能会出现left > right的现象.40/45惨痛教训. left和right必须在出现新的大于maxAns时才能够修改
            right = i;
        }
    }
    return maxAns;
}
vector MaxSubMatrix(vector> &matrix)
{
    int m = matrix.size();
    int n = matrix[0].size();
    vector b(n);
    vector res(4);
    int ans = INT_MIN;
    for(int i=0; i ans)
            {
                ans = max;
                res[0] = i;
                res[1] = left;
                res[2] = j;
                res[3] = right;
            }
        }
    }
    return res;
}

欢迎大家访问我的个人博客 --- 乔治的编程小屋,和我一起为大厂offer努力吧!