求可任意翻转一段子序列后的最大子序列和
概述
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: 求可任意翻转一段子序列后的最大子序列和