题意：给定你一个长度为 $ n $ 的序列 $ a_1, a_2, a_3, \cdot\cdot\cdot a_n $, 找出其中一段连续的子序列, 使得这段子序列的和最大。
思路：考虑 DP, 设 $ dp_i $ ：以 $ a_i $ 结尾的最大子序和, 因为需要找连续的一段, 所以 $ dp_i = max(dp_{i - 1} + a_i, a_i) $, 即：如果 $ dp_{i - 1} > 0 $, 就将 $ dp_{i - 1} $ 加到 $ dp_i $ 里面。
点击查看代码
#include <bits/stdc++.h>
inline int read() {
bool sym = false; int res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
int main() {
int T = read();
for (int i = 1; i <= T; i++) {
int n = read();
std::vector<int> a(n + 1);
std::vector<int> dp(n + 1);
for (int j = 1; j <= n; j++) {
a[j] = read();
}
for (int j = 1; j <= n; j++) {
dp[j] = a[j];
}
int max = (int) -2e9, p = 1, l = 1, r = 1;
for (int j = 1; j <= n; j++) {
if (dp[j - 1] > 0) {
dp[j] += dp[j - 1];
} else {
p = j;
}
if (dp[j] > max) {
max = dp[j]; l = p; r = j;
}
}
printf("Case %d:\n%d %d %d\n", i, max, l, r);
}
return 0;
}
接下来考虑一个新的问题：如果限制连续子序列的长度 $ \le m $, 此问题该如何求解？
思路：将问题转化为：对于任意的 $ i(1 \le i \le n) $, 找到一个 $ j(i - j \le m) $, 满足 $ \Sigma_{k = j}^i a_i $ 最大。若枚举终点 $ i $, 然后每一次向前检查 $ m $ 个数字, 那么时间复杂度为 $ O(nm) $, 对于 $ \le 5 \times 10^5 $ 的 $ n、m $, 这样的复杂度显然是无法接受的。考虑到枚举每一个终点 $ i $ 时, 只需要找到左边 $ 1 \sim m $ 范围内的前缀和的最小值(设前缀和数组为 $ sum_i $, 那么对于每一个位置 $ i $, 需要找到一个 $ j (i - j \le m) $, 满足 $ sum_i - sum_{j - 1} $ 最大), 这里可以用单调队列维护一个长度为 $ m $ 的滑动窗口。每个元素入队、出队一次, 总的时间复杂度为 $ O(n) $。
点击查看代码
#include <bits/stdc++.h>
inline int read() {
bool sym = false; int res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
int main() {
int n = read(), m = read();
std::vector<long long> p(n + 1);
for (int i = 1; i <= n; i++) {
scanf("%lld", &p[i]);
}
std::vector<long long> pref(n + 1);
for (int i = 1; i <= n; i++) {
pref[i] = pref[i - 1] + p[i];
}
std::deque<long long> qmin;
long long max = pref[1];
std::vector<long long> value(n + 1);
for (int i = 1; i < n; i++) {
while (qmin.size() && pref[i] <= pref[qmin.back()]) {
qmin.pop_back();
}
qmin.push_back(i);
if (i >= m) {
while (qmin.size() && qmin.front() < i + 1 - m) {
qmin.pop_front();
}
}
value[i + 1] = pref[qmin.front()];
}
for (int i = 2; i <= n; i++) {
max = std::max(max, pref[i] - value[i]);
}
printf("%lld\n", max);
return 0;
}