题意：给定一个长度为 $ n $ 的序列 $ a_1, a_2, a_3, \cdot\cdot\cdot a_n (-10^3 \le a_i \le 10^3, 1 \le n \le 10^5) $, 找出其中一个和最大的连续子段, 并输出最大的和、该子段的起始下标。
思路一：DP
设 $ f_i $ : 以 $ a_i $ 结尾的最大子序和。因为需要选择连续的子段, 因此, $ f_i = max(f_i - 1 + a_i, a_i) $。
点击查看代码
#include <bits/stdc++.h>
inline int read() {
int res = 0; char ch = getchar(); bool sym = false;
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> f(n + 1);
std::vector<int> a(n + 1);
for (int j = 1; j <= n; j++) {
a[j] = read();
}
for (int j = 1; j <= n; j++) {
f[j] = a[j];
}
int max = (int) -2e9;
int l = 1, r = 1, p = 1;
for (int j = 1; j <= n; j++) {
if (f[j - 1] >= 0) {
f[j] += f[j - 1];
} else {
p = j;
// 下一个可能的子段的左端点是 j
}
if (f[j] > max) {
max = f[j]; l = p; r = j;
}
}
printf("Case %d:\n%d %d %d\n", i, max, l, r);
}
return 0;
}
接下来考虑：如果限制子段的长度 $ \le k $, 该问题应如何解决。
标签：10,le,队列,max,int,ch,cdot,子序,单调 From： https://www.cnblogs.com/LDUyanhy/p/17717927.html