A18895. 最大子段和（前缀和 + 贪心）
填空题
中等
知识点
题目描述
最大子段和（前缀和 + 贪心）
题目描述
给定一个整数数组，求连续子数组的最大和（经典最大子数组和）。
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
const int INF = 0x3f3f3f3f;
int a[N], s[N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
s[i] = s[i-1] + a[i];
}
int min_s = s[0];
int ans = -INF;
for (int r = 1; r <= n; r++)
{
ans = max(ans, s[r] - min_s);
min_s = min(min_s, s[r]); // 更新最小前缀和
}
cout << ans << endl;
return 0;
}答案解析
思路利用前缀和：
(s[r]-s[l-1]) 就是 ([l,r]) 和。
遍历右端点 r，维护前面最小的前缀和 (min_s)，则：
(text{当前最大和} = s[r] - min_s)
上一题
下一题