求可任意翻转一段子序列后的最大子序列和

    
        标签：
        
            笔试算法题
        
    发布于：2022-03-16 11:46:27
    编辑于：2022-03-16 20:10:53
    浏览量：788

概述

https://www.bilibili.com/video/BV19b4y1W7nL/

https://leetcode-cn.com/circle/discuss/v0YJ8z/

最大子段和是一个经典问题，即对于一个数组找出其和最大的子数组。

现在允许你在求解该问题之前翻转这个数组的连续一段（如翻转{1,2,3,4,5,6}的第三个到第五个元素组成的子数组得到的是{1,2,5,4,3,6}），则翻转后该数组的最大子段和最大能达到多少？

O(n^2) 暴力解法

基本的想法是，暴力遍历翻转子序列的所有可能前后端点，算出该区间和，再加上前面的最大子段和即可。

最大字段和可以用动态规划 O(n) 搞定。

dp[n] 表示前 n 个中的最大子段和，显然 dp[i] = max(dp[i-1], 以第 i 个元素结尾的最大和) 。

这里有个小坑是 ans 的初始值需要设为 INT_MIN，不能设置为 0，因为可能出现全负数的情况。

#include <bits/stdc++.h>
using namespace std;

int main () {
    int n; cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i ++) cin >> nums[i];
    vector<int> maxSums(n), sums(n);
    int ans = INT_MIN;
    for (int i = 0, s = 0; i < n; i ++) {
        s += nums[i];
        if (s < 0) s = 0;  // 以第 i 个元素结尾的最大和
        maxSums[i] = i != 0 ? max(maxSums[i-1], s) : s;  // 算出最大子段和
        sums[i] = i != 0 ? sums[i-1] + nums[i] : nums[i];  // 算出前缀和
        for (int j = 0; j < i; j ++) {
            ans = max(ans, sums[i] - sums[j] + maxSums[j]);
        }
    }
    cout << ans;
}

O(n) 优化

注意看内层循环：

for (int j = 0; j < i; j ++) {
    ans = max(ans, sums[i] - sums[j] + maxSums[j]);
}

我们可以记录一下 - sums[j] + maxSums[j] 的最大值，这样就不需要每次都遍历了。

即：

maxSuffix[i] = i != 0 ? max(maxSuffix[i-1], - sums[i] + maxSums[i]) : 0;
ans = max(ans, sums[i] + maxSuffix[i]);

全部的代码：

#include <bits/stdc++.h>
using namespace std;

int main () {
    int n; cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i ++) cin >> nums[i];
    vector<int> maxSums(n), sums(n), maxSuffix(n);
    int ans = 0;
    for (int i = 0, s = 0; i < n; i ++) {
        s += nums[i];
        if (s < 0) s = 0;
        maxSums[i] = i != 0 ? max(maxSums[i-1], s) : s;
        sums[i] = i != 0 ? sums[i-1] + nums[i] : nums[i];
        maxSuffix[i] = i != 0 ? max(maxSuffix[i-1], - sums[i] + maxSums[i]) : 0;
        ans = max(ans, sums[i] + maxSuffix[i]);
    }
    cout << ans;
}

O(n) 双向 dp

https://t.bilibili.com/634764976388571176

左边的 ldp[i] 记录 0~i 中最大连续子段和（可以不包含第 i 个元素）。

右边的 rdp[i] 有两种选择：

像 ldp 一样，记录 i~n 中最大连续子段和（可以不包含第 i 个元素）。
rdp[i] 表示从第 i 个元素开始的最大连续子段和（必须包含第 i 个元素）。

下面给出的解法是用的情况二。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    vector<int> ldp(n), rdp(n);
    for (int i = 0, s = 0; i < n; i++) {
        s += nums[i];
        if (s < 0) s = 0;
        ldp[i] = i != 0 ? max(ldp[i - 1], s) : max(0, nums[i]);
    }
    for (int i = n - 1; i >= 0; i--) {
        rdp[i] = i != n - 1 ? max(nums[i], rdp[i + 1] + nums[i]) : nums[i];
    }
    int ans = INT_MIN;
    for (int i = 0; i < n - 1; i++) {
        ans = max(ans, ldp[i] + rdp[i + 1]);
    }
    cout << ans;
}

注意 corner case 的情况。

Links: 求可任意翻转一段子序列后的最大子序列和