【动规】最大子数组和、积

最大子数组和

经典1D动态规划。

Kadane algorithm, time = \(O(n)\):

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        int dp = nums[0]; // space optimization
        for (int i = 1; i < nums.size(); i++) {
            dp = max(dp + nums[i], nums[i]);
            ans = max(ans, dp);
        }
        return ans;
    }
};

最大子矩阵

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

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

2D拓展。

但并不是用2D前缀和，反而是1D列前缀和，再枚举列起点和终点，再对行做1D Kadane。这样能够时间复杂度\(O(n^2m)\)。

另外不只要求返回和，还要返回坐标，需要额外的记录和判断。

class Solution {
public:
    vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> s(m + 1, vector<int>(n, 0)); // column-wise prefix sum
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < n; j++) {
                s[i][j] = s[i-1][j] + matrix[i - 1][j];
            }
        }
        int mx = matrix[0][0];
        vector<int> ans(4, 0);
        // row start/end, O(n^2)
        for (int r1 = 0; r1 < m; r1++) {
            for (int r2 = r1 + 1; r2 <= m; r2++) {
                // kadane on each row, O(m)
                int dp = s[r2][0] - s[r1][0];
                int start = 0; // start index of max-sum-subarray
                if (dp > mx) mx = dp, ans = {r1, 0, r2 - 1, 0};
                for (int c = 1; c < n; c++) {
                    int v = s[r2][c] - s[r1][c];
                    if (dp + v > v) {
                        dp = dp + v;
                    } else {
                        dp = v;
                        start = c;
                    }
                    if (dp > mx) mx = dp, ans = {r1, start, r2 - 1, c};
                }
            }
        }
        return ans;
    }
};

乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

乘法拓展，如果所有数都是正数，乘法仍然保持Kadane的动态规划条件，可以直接用。

然而如果有负数，就得再记录一个最小值，因为有可能子数组包含偶数个负数，积仍为正数。

Variant of Kadane, time = \(O(n)\):

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int ans = nums[0];
        int mx = nums[0], mn = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            int old_mx = mx;
            mx = max(mx * nums[i], max(mn * nums[i], nums[i]));
            mn = min(mn * nums[i], min(old_mx * nums[i], nums[i]));
            ans = max(ans, mx);
        }
        return ans;
    }
};