[Algo] 子数组最大累加和2

1. 乘积最大子数组

// 1. 乘积最大子数组
// https://leetcode.cn/problems/maximum-product-subarray/
int maxProduct(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp_min(n), dp_max(n);
    dp_min[0] = nums[0]; dp_max[0] = nums[0];
    int ans = dp_max[0];
    for (int i = 1; i < n; i++)
    {
        dp_min[i] = min(nums[i], min(nums[i] * dp_min[i - 1], nums[i] * dp_max[i - 1]));
        dp_max[i] = max(nums[i], max(nums[i] * dp_min[i - 1], nums[i] * dp_max[i - 1]));
        ans = max(ans, dp_max[i]);
    }
    return ans;
}

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

// 2. 子序列累加和必须被7整除的最大累加和
int maxSumDividedBy7(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> dp(n + 1, vector<int>(7));
    // dp[i][j]: 前n个数中累加和模7为j的最大累加和, -1表示不存在
    dp[0][0] = 0;
    for (int j = 1; j < 7; j++) dp[0][j] = -1;
    for (int i = 1; i <= n; i++)
    {
        int cur = nums[i - 1] % 7;
        for (int j = 0; j < 7; j++)
        {
            int need = j >= cur ? j - cur : j + 7 - cur;
            dp[i][j] = dp[i - 1][j];
            if (dp[i - 1][need] != -1) dp[i][j] = max(dp[i - 1][j], nums[i - 1] + dp[i - 1][need]);
        }
    }
    return dp[n][0];
}

3. 魔法卷轴i

// 3. 魔法卷轴i
// 给定一个数组nums，其中可能有正、负、0
// 每个魔法卷轴可以把nums中连续的一段全变成0
// 你希望数组整体的累加和尽可能大
// 卷轴使不使用、使用多少随意，但一共只有2个魔法卷轴
// 请返回数组尽可能大的累加和
int magicScroll(vector<int> &nums)
{
    int p0 = 0;
    for (int num : nums) p0 += num; // p0: 不使用魔法卷轴的累加和

    vector<int> dp(nums.size());  // dp[i]: nums[0...i]使用一次魔法卷轴的最大累加和
    int prefix = nums[0], maxPrefix = max(0, nums[0]);
    for (int i = 1; i < nums.size(); i++)
    {
        dp[i] = max(nums[i] + dp[i - 1], maxPrefix);
        prefix += nums[i];
        maxPrefix = max(maxPrefix, prefix);
    }
    int p1 = dp[nums.size() - 1]; // p1: 使用1次魔法卷轴的最大累加和

    vector<int> dp_(nums.size()); // dp_[i]: nums[i...n-1]使用一次魔法卷轴的最大累加和
    dp_[nums.size() - 1] = 0;
    int suffix = nums[nums.size() - 1], maxSuffix = max(0, nums[nums.size() - 1]);
    for (int i = nums.size() - 2; i >= 0; i--)
    {
        dp_[i] = max(nums[i] + dp_[i + 1], maxSuffix);
        suffix += nums[i];
        maxSuffix = max(maxSuffix, suffix);
    }
    int p2 = INT32_MIN;
    for (int k = 1; k < nums.size() - 1; k++)
    p2 = max(p2, nums[k] + dp[k - 1] + dp_[k + 1]); // p2: 使用2次魔法卷轴的最大累加和

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

4. 魔法卷轴ii

// 4. 魔法卷轴ii
// 给定一个数组nums，
// 现在允许你随意选择数组连续一段进行翻转，也就是子数组逆序的调整
// 比如翻转[1,2,3,4,5,6]的[2~4]范围，得到的是[1,2,5,4,3,6]
// 返回必须随意翻转1次之后，子数组的最大累加和
int MagicScroll(vector<int> &nums)
{
    int n = nums.size();
    vector<int> original(n);
    original[n - 1] = nums[n - 1]; // original[i]: nums[i...n-1]中以i为开始位置的最大累加和
    for (int i = n - 2; i >= 0; i--) original[i] = max(nums[i], nums[i] + original[i + 1]);

    int end = nums[0], maxEnd = nums[0], ans = INT32_MIN;
    // end: nums[0...i]中以i为结束位置的最大累加和
    // maxEnd: nums[0...i]中的最大累加和
    for (int i = 1; i < n; i++)
    {
        ans = max(ans, maxEnd + original[i]);
        end = max(nums[i], nums[i] + end);
        maxEnd = max(maxEnd, end);
    }

    return max(ans, maxEnd);
}