洛谷 P1115 最大子段和：从暴力到最优的推导与实现
对于最大子段和问题，最直观的思路是枚举所有可能的区间端点：
for (int left = 1; left <= n; ++left) {
for (int right = left; right <= n; ++right) {
int range_sum = prefix[right] - prefix[left - 1];
result = max(result, range_sum);
}
}
然而这种做法的时间复杂度为 O(n^2)，无法通过数据范围较大的测试。
深入分析：若将序列转化为前缀和形式，则任意子段 [l, r] 的和可表示为 S_r - S_{l-1}。对于固定的右端点 r，欲使子段和最大，只需让 S_{l-1} 尽可能小。因此问题转化为：在遍历过程中动态维护前缀和的最小值。
基础版本：前缀和 + 最小值数组
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int arr[MAXN];
int prefix[MAXN];
int min_prefix[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> arr[i];
prefix[i] = prefix[i - 1] + arr[i];
min_prefix[i] = min(min_prefix[i - 1], prefix[i]);
}
int answer = -2e4;
for (int i = 1; i <= n; ++i) {
answer = max(answer, prefix[i] - min_prefix[i - 1]);
}
cout << answer;
return 0;
}
优化一：消除原数组
输入处理完毕后，原数组元素不再被直接使用，可用临时变量替代：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int prefix[MAXN];
int min_prefix[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
int value;
cin >> value;
prefix[i] = prefix[i - 1] + value;
min_prefix[i] = min(min_prefix[i - 1], prefix[i]);
}
int answer = -2e4;
for (int i = 1; i <= n; ++i) {
answer = max(answer, prefix[i] - min_prefix[i - 1]);
}
cout << answer;
return 0;
}
优化二：合并循环
两个循环均遍历 1 \sim n，可合并以降低常数因子：
#include <bits/stdc.h>
using namespace std;
const int MAXN = 2e5 + 10;
int prefix[MAXN];
int min_prefix[MAXN];
int answer = -2e4;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
int value;
cin >> value;
prefix[i] = prefix[i - 1] + value;
min_prefix[i] = min(min_prefix[i - 1], prefix[i]);
answer = max(answer, prefix[i] - min_prefix[i - 1]);
}
cout << answer;
return 0;
}
优化三：压缩最小值数组
每次仅用到 M_{i-1}，无需保存整个历史，单个变量足矣：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int prefix[MAXN];
int min_so_far = 0;
int answer = -2e4;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
int value;
cin >> value;
prefix[i] = prefix[i - 1] + value;
answer = max(answer, prefix[i] - min_so_far);
min_so_far = min(min_so_far, prefix[i]);
}
cout << answer;
return 0;
}
优化四：完全压缩至 O(1) 空间
同理，前缀和数组也可被单个滚动变量替代：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int current_sum = 0;
int min_so_far = 0;
int answer = -2e4;
for (int i = 0; i < n; ++i) {
int value;
cin >> value;
current_sum += value;
answer = max(answer, current_sum - min_so_far);
min_so_far = min(min_so_far, current_sum);
}
cout << answer;
return 0;
}
最终版本时间复杂度 O(n)，额外空间复杂度 O(1)，为最优解。
