AcWing 3652. 最大连续子序列
原题链接
简单
作者:
starky-_-
,
2023-03-22 17:06:16
,
所有人可见
,
阅读 220
一维的状态表示
f[i] 表示以i结尾的连续子序列的和属性为Max
状态转移方程:
f[i] = max(a[i], a[i] + f[i - 1])
下面如何保存这个最大的连续子序列的开始位置和结束位置?
1. 如何寻找右端点?
首先初始化为0,在更新最大值的时候,将r更新为对应的f[i]
的下标 i
2. 最 简单 麻烦的是寻找左端点
首先初始化为0
在更新f[i]
的时候,如果f[i - 1] < 0
也就是说f[i] = a[i]
的时候
这时候就相当于去掉了前面所有的数,从a[i]
开始寻找最大连续的子序列
这时先用pre
保存当前的i
的值,在更新res
的时候根据pre
更新l
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N];
int f[N];
int main()
{
while (cin >> n)
{
int l = 0, r = 0;
for (int i = 0; i < n; ++ i) scanf("%d", &a[i]);
f[0] = a[0];
int res = a[0];
int pre = 0;
for (int i = 1; i < n; ++ i)
{
if (f[i - 1] < 0)
{
pre = i; // 记录左起点
f[i] = a[i];
}
else f[i] = a[i] + f[i - 1];
if(res < f[i]) res = f[i], r = i, l = pre;// 更新答案,res, l, r
}
if (res < 0) l = r = res = 0;// 如果k个元素都是负数
printf("%d %d %d\n", res, l, r);
}
return 0;
}