最大子数组和问题

题设

给定一个数组，求子数组的最大和

leetcode常见题目，我第一反应总是前缀和。。。（跳不出思维定势啊）

暴力办法

1. 选取左右端点，然后暴力计算两个端点区间内的和，时间复杂度O(N ^ 3)
2. （前缀和优化）利用前缀和数组，即prefixSum(j) - prefixSum(i)计算区间和，时间复杂度O(N ^ 2)，空间复杂度O(N)

显然这个办法不是最优的办法，因为没有利用到这个问题的特性吧，局部解必定是全局最优解的一部分

例如

​ 图1 一维子数组最大和求解

动态规划

这个问题肯定可以通过动态规划求解，因为全局的解和局部的解有很清晰的关系，只要局部解是可以接受的（该问题为和大于0），都可以考虑纳入到全局最优解中

但是dp数组怎么设定呢？（一直搞不懂dp数组在不同问题的设定方式啊。。。泪奔）

这里把dp数组设置为以i为终点的子数组的最大和

例如上述图1

dp[1] = 1 + 3 = 4

dp[2] = 3

dp[3] = 8 如此类推

之后答案就是dp数组中的最大值

这里由于dp数组中，每一项只与前一项相关，所以也不需要开一个数组了，空间复杂度可以优化到O(1)

代码实现如下

1
2
3
4
5
6
7
8
9

int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int dp = nums[0], ans = dp;
        for(int i = 1; i < n; i++) {
            dp = max(dp + nums[i], nums[i]);
            ans = max(dp, ans); 
        }
        return ans;
}

升维拓展

把问题拓展到二维数组，求最大子矩阵的和

这个问题的暴力实现复杂度应该是O(N ^ 6)（左端点选择为O(N ^ 2)，右端点选择为O(N ^ 2)， 矩阵和计算为O(N ^ 2)）

利用上面讲的方法，把一列压缩为dp中的一个元素，即dp[i]的时间复杂度为O(N)，之后选行，分别考虑第一行，第一第二行，第一第二第三行…..，第一第二第三…第n行，第二行，第二第三行, ……, 第n行，总共N ^ 2，故最终时间复杂度为O(N ^ 3)

如图所示

​ 图2-1 二维子矩阵最大和求解

​ 图2-2 二维子矩阵最大和求解

​ 图2-3 二维子矩阵最大和求解

同时，值得注意的是，如上图，在计算第一行以及第一行和第二行，第一第二第三行的时候，前者的dp[i]是可以留到后面使用的，所以dp的初始化在第一重循环内完成

代码实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int maxSubMatrix(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    int maxSum = INT_MIN;
    for (int i = 0; i < rows; i++) {
        vector<int> dp(cols, 0); //dp[k]表示从第i到第j行，以k列为结尾的子数组的最大和
        for (int j = i; j < rows; j++) {
            int tmp = 0;
            for (int k = 0; k < cols; k++) {
                dp[k] += matrix[j][k];
                if (tmp >= 0)
                    tmp += dp[k];
                else
                    tmp = dp[k];
                maxSum = max(maxSum, tmp);
            }
        }
    }
    return maxSum;
}