子数组最大累加和（下）

子数组最大累加和（下）

152. 乘积最大子数组

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxProduct(vector<int> &nums) {
        int res = nums[0];
        // 以 i 位置结尾的子数组乘积的最大值和最小值
        int minDP = nums[0];
        int maxDP = nums[0];
        // 最大值可能是当前元素
        // 或者是以 i-1 位置结尾的最小乘积与 nums[i] 相乘（负数乘负数）
        // 或者以 i-1 位置结尾的最大乘积与 nums[i] 相乘
        // 在递推过程中，记录以 i-1 结尾的子数组乘积的最值
        for (int i = 1, curMin, curMax; i < nums.size(); ++i) {
            curMin = min(nums[i], min(nums[i] * minDP, nums[i] * maxDP));
            curMax = max(nums[i], max(nums[i] * minDP, nums[i] * maxDP));
            minDP = curMin;
            maxDP = curMax;
            res = max(res, maxDP);
        }
        return res;
    }
};

子序列累加和必须被7整除的最大累加和

给定一个非负数组 nums，可以任意选择数字组成子序列，但是子序列的累加和必须被7整除，返回最大累加和。

#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdlib>

using namespace std;

class Solution {

public:
    // 暴力递归，作为验证方法
    int maxSum1(vector<int> &nums) {
        return recursive(nums, 0, 0);
    }

    int recursive(vector<int> &nums, int i, int s) {
        if (i == nums.size())
            return s % 7 == 0 ? s : 0;
        return max(recursive(nums, i + 1, s), recursive(nums, i + 1, s + nums[i]));
    }

    // 正式方法，时间复杂度 O(n)
    int maxSum2(vector<int> &nums) {
        int n = nums.size();
        // dp[i][j] 表示 nums 前 i 个数形成的子序列，子序列累加和模 7 等于 j
        // 这样的子序列最大累加和是多少
        // dp[i][j] == -1 表示不存在
        vector<vector<int>> dp(n + 1, vector<int>(7, -1));
        // i = 0 的情况，只有模 7 为 0 的情况存在，且累加和为 0
        dp[0][0] = 0;
        fill(dp[0].begin() + 1, dp[0].end(), -1);
        // i > 0 的情况
        for (int i = 1; i <= n; i++) {
            // 当前数字
            int cur = nums[i - 1];
            // 当前数字模 7 的余数
            int reminder = nums[i - 1] % 7;
            for (int j = 0; j < 7; j++) {
                // 子序列不要当前数字的情况，最大累加和就是之前的
                dp[i][j] = dp[i - 1][j];
                // 还需要的余数
                int need = (7 + j - reminder) % 7;
                // 子序列要当前数字的情况
                if (dp[i - 1][need] != -1)
                    dp[i][j] = max(dp[i][j], dp[i - 1][need] + cur);
            }
        }
        return dp[n][0];
    }
};

vector<int> randomArray(int n, int v) {
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        arr[i] = rand() % v;
    return arr;
}

int main() {
    Solution s;
    int n = 15;
    int v = 30;
    int testTime = 20000;
    cout << "测试开始" << endl;
    for (int i = 0; i < testTime; i++) {
        int len = rand() % n + 1;
        vector<int> nums = randomArray(len, v);
        int ans1 = s.maxSum1(nums);
        int ans2 = s.maxSum2(nums);
        if (ans1 != ans2) cout << "出错了!" << endl;
    }
    cout << "测试结束" << endl;
}

魔法卷轴

给定一个数组 nums，其中可能有正、负、0。每个魔法卷轴可以把nums中连续的一段全变成0，你希望数组整体的累加和尽可能大。卷轴使不使用、使用多少随意，但一共只有2个魔法卷轴，返回数组尽可能大的累加和。

#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdlib>

using namespace std;

class Solution {
public:
    // 暴力递归
    int maxSum1(const vector<int> &nums) {
        int n = nums.size();
        // 不用卷轴
        int p1 = 0;
        for (int num: nums) p1 += num;
        // 用一个卷轴
        int p2 = mustOneScroll(nums, 0, n - 1);
        // 用两个卷轴
        int p3 = INT_MIN;
        for (int i = 0; i <= n - 2; i++)
            p3 = max(p3, mustOneScroll(nums, 0, i) + mustOneScroll(nums, i + 1, n - 1));
        return max(p1, max(p2, p3));
    }

    // nums[start...end] 范围上用一次卷轴的最大累加和
    int mustOneScroll(const vector<int> &nums, int start, int end) {
        int res = INT_MIN;
        // [l, r] 变成 0
        for (int l = start; l <= end; l++) {
            for (int r = l; r <= end; r++) {
                int curAns = 0;
                // 累加 [l, r] 范围外的
                for (int i = start; i < l; i++)
                    curAns += nums[i];
                for (int i = r + 1; i <= end; i++)
                    curAns += nums[i];
                res = max(res, curAns);
            }
        }
        return res;
    }

    // 正式方法，时间复杂度 O(n)
    int maxSum2(const vector<int> &nums) {
        int n = nums.size();
        if (n == 0) return 0;

        // 不用卷轴
        int p1 = 0;
        for (int num: nums) p1 += num;

        // prefix[i]: 0 ~ i 范围上用一次卷轴的情况下，0 ~ i 范围上整体最大累加和多少
        vector<int> prefix(n);
        // 前缀和
        int prefixSum = nums[0];
        // 前缀和的最大值
        int maxPrefixSum = max(0, nums[0]);
        for (int i = 1; i < n; i++) {
            // 在 i 位置之前已经用过卷轴：最大累加和就要加上当前数字，prefix[i - 1] + nums[i]
            // 在 i 位置之前没有用过卷轴：最大累加和就是之前前缀和的最大值，使用卷轴的部分是最大前缀和出现的地方到当前位置
            prefix[i] = max(prefix[i - 1] + nums[i], maxPrefixSum);
            // 更新
            prefixSum += nums[i];
            maxPrefixSum = max(maxPrefixSum, prefixSum);
        }
        // 用一个卷轴
        int p2 = prefix[n - 1];

        // suffix[i] : i ~ n - 1 范围上用一次卷轴的情况下，i ~ n - 1 范围上整体最大累加和多少
        vector<int> suffix(n);
        int suffixSum = nums[n - 1];
        int maxSuffixSum = max(0, suffixSum);
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = max(nums[i] + suffix[i + 1], maxSuffixSum);
            suffixSum += nums[i];
            maxSuffixSum = max(maxSuffixSum, suffixSum);
        }
        // 用两个卷轴
        int p3 = INT_MIN;
        for (int i = 1; i < n; i++)
            p3 = max(p3, prefix[i - 1] + suffix[i]);

        return max(p1, max(p2, p3));
    }
};

vector<int> randomArray(int n, int v) {
    vector<int> ans(n);
    for (int i = 0; i < n; i++)
        ans[i] = rand() % (v * 2 + 1) - v;
    return ans;
}

int main() {
    Solution s;
    int n = 50;
    int v = 100;
    int testTime = 10000;
    cout << "测试开始" << endl;
    for (int i = 0; i < testTime; i++) {
        int len = rand() % n;
        vector<int> nums = randomArray(len, v);
        int ans1 = s.maxSum1(nums);
        int ans2 = s.maxSum2(nums);
        if (ans1 != ans2) {
            cout << "出错了!" << endl;
        }
    }
    cout << "测试结束" << endl;
}

689. 三个无重叠子数组的最大和

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int> &nums, int k) {
        int n = nums.size();
        // sums[i]: 以 i 开头并且长度为 k 的子数组的累加和
        vector<int> sums(n);
        for (int l = 0, r = 0, sum = 0; r < n; r++) {
            sum += nums[r];
            if (r - l + 1 == k) {
                sums[l] = sum;
                sum -= nums[l];
                l++;
            }
        }

        // prefix[i]: 0 ~ i 范围上所有长度为 k 的子数组中，拥有最大累加和的子数组，是以什么位置开头的
        vector<int> prefix(n);
        // prefix[0, k-2] 位置的子数组长度都没到 k，不需要填
        // prefix[k-1] 子数组长度为 k，以 0 开头
        for (int l = 1, r = k; r < n; l++, r++) {
            // sums[l] 是 r++ 后新增加的，需要考虑的长度为 k 的子数组累加和
            if (sums[l] > sums[prefix[r - 1]]) {
                // 新增的更大
                prefix[r] = l;
            } else {
                // 原来在 0 ~ r - 1 上最大累加和更大
                prefix[r] = prefix[r - 1];
            }
        }

        // suffix[i]: i ~ n - 1 范围上所有长度为 k 的子数组中，拥有最大累加和的子数组，是以什么位置开头的
        vector<int> suffix(n);
        suffix[n - k] = n - k;
        for (int l = n - k - 1; l >= 0; l--) {
            if (sums[l] >= sums[suffix[l + 1]]) {
                suffix[l] = l;
            } else {
                suffix[l] = suffix[l + 1];
            }
        }

        int a = 0, b = 0, c = 0, maxSum = 0;
        // 中间的子数组 [i, j] 长度 k
        for (int p, s, i = k, j = 2 * k - 1, sum; j < n - k; i++, j++) {
            // [0, i - 1] 上的最大累加和的子数组以 p 开头
            p = prefix[i - 1];
            // [i + 1, n - 1] 上的最大累加和的子数组以 s 开头
            s = suffix[j + 1];
            sum = sums[p] + sums[i] + sums[s];
            if (sum > maxSum) {
                maxSum = sum;
                a = p;
                b = i;
                c = s;
            }
        }
        return {a, b, c};
    }
};

可以翻转1次的情况下子数组最大累加和

给定一个数组 nums，现在允许你随意选择数组连续一段进行翻转，也就是子数组逆序的调整。返回必须随意翻转 1 次之后，子数组的最大累加和。

#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;

class Solution {
public:
    // 暴力方法
    int maxSumReverse1(vector<int> &nums) {
        int res = INT_MIN;
        for (int l = 0; l < nums.size(); l++) {
            for (int r = l; r < nums.size(); r++) {
                reverse(nums, l, r);
                res = max(res, maxSum(nums));
                reverse(nums, l, r);
            }
        }
        return res;
    }

    // nums[l...r] 范围上的数字进行逆序调整
    void reverse(vector<int> &nums, int l, int r) {
        while (l < r)
            swap(nums[l++], nums[r--]);
    }

    // 返回子数组最大累加和
    int maxSum(const vector<int> &nums) {
        int n = nums.size();
        int res = nums[0];
        for (int i = 1, pre = nums[0]; i < n; i++) {
            pre = max(nums[i], pre + nums[i]);
            res = max(res, pre);
        }
        return res;
    }

    // 正式方法，时间复杂度 O(n)
    int maxSumReverse2(vector<int> &nums) {
        int n = nums.size();
        // start[i]: 以 i 开头的子数组中，最大累加和是多少
        vector<int> start(n);
        start[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--)
            start[i] = max(nums[i], nums[i] + start[i + 1]);

        int res = start[0];
        // end: 子数组必须以 i - 1 结尾，其中的最大累加和
        int end = nums[0];
        // 0 ~ i - 1 上以某个位置结尾的子数组的最大累加和
        int maxEnd = nums[0];
        for (int i = 1; i < n; i++) {
            res = max(res, maxEnd + start[i]);
            end = max(nums[i], end + nums[i]);
            maxEnd = max(maxEnd, end);
        }
        // 不用翻转的情况
        res = max(res, maxEnd);
        return res;
    }
};

vector<int> randomArray(int n, int v) {
    vector<int> ans(n);
    for (int i = 0; i < n; i++)
        ans[i] = rand() % (v * 2 + 1) - v;
    return ans;
}

int main() {
    Solution s;
    int n = 50;
    int v = 200;
    int testTime = 20000;
    cout << "测试开始" << endl;
    for (int i = 0; i < testTime; i++) {
        int len = rand() % n + 1;
        vector<int> arr = randomArray(len, v);
        int ans1 = s.maxSumReverse1(arr);
        int ans2 = s.maxSumReverse2(arr);
        if (ans1 != ans2)
            cout << "出错了!" << endl;
    }
    cout << "测试结束" << endl;
}

删掉1个数字后长度为k的子数组最大累加和

给定一个数组 nums，求必须删除一个数字后的新数组中，长度为 k 的子数组最大累加和，删除哪个数字随意

#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;

class Solution {
public:
    // 暴力方法
    int maxSum1(vector<int> &nums, int k) {
        int n = nums.size();
        if (n <= k) return 0;
        int res = INT_MIN;
        for (int i = 0; i < n; i++) {
            vector<int> rest = deleteElement(nums, i);
            res = max(res, lenKMaxSum(rest, k));
        }
        return res;
    }

    // 删掉 index 位置的元素，然后返回新数组
    vector<int> deleteElement(vector<int> &nums, int index) {
        vector<int> res;
        for (int j = 0; j < nums.size(); j++)
            if (j != index)
                res.push_back(nums[j]);
        return res;
    }

    // 枚举每一个子数组找到最大累加和
    int lenKMaxSum(vector<int> &nums, int k) {
        int n = nums.size();
        int res = INT_MIN;
        for (int i = 0; i <= n - k; i++) {
            int cur = 0;
            for (int j = i, cnt = 0; cnt < k; j++, cnt++)
                cur += nums[j];
            res = max(res, cur);
        }
        return res;
    }

    // 正式方法：时间复杂度 O(N)
    int maxSum2(vector<int> &nums, int k) {
        int n = nums.size();
        if (n <= k) return 0;
        // 单调队列: 维持窗口内最小值的更新结构
        vector<int> queue(n);
        int l = 0, r = 0;
        // 窗口累加和
        long sum = 0;
        int res = INT_MIN;
        for (int i = 0; i < n; i++) {
            // i 位置进入单调队列
            while (l < r && nums[queue[r - 1]] >= nums[i])
                r--;
            queue[r++] = i;
            sum += nums[i];
            if (i >= k) {
                res = max(res, (int) (sum - nums[queue[l]]));
                // 如果单调队列最左侧的位置过期了，从队列中弹出
                if (queue[l] == i - k) l++;
                sum -= nums[i - k];
            }
        }
        return res;
    }
};

// 生成长度为 n，值在 [-v, +v] 之间的随机数组
vector<int> randomArray(int n, int v) {
    vector<int> ans(n);
    for (int i = 0; i < n; i++)
        ans[i] = rand() % (2 * v + 1) - v;
    return ans;
}

int main() {
    Solution s;
    int n = 200;
    int v = 1000;
    int testTimes = 10000;
    cout << "测试开始" << endl;
    for (int i = 0; i < testTimes; i++) {
        int len = rand() % n + 1;
        vector<int> nums = randomArray(len, v);
        int k = rand() % n + 1;
        int ans1 = s.maxSum1(nums, k);
        int ans2 = s.maxSum2(nums, k);
        if (ans1 != ans2)
            cout << "出错了!" << endl;
    }
    cout << "测试结束" << endl;
}