AcWing 3652. 最大连续子序列
原题链接
简单
作者:
Polaris6G
,
2023-03-22 17:07:11
,
所有人可见
,
阅读 101
C++ 代码
#include <cstdio>
int main(){
int K;
while(scanf("%d", &K) != EOF){
//这里解释下,EOF,即End Of File,表示资料源无更多的资料可读取。
int f[K], L[K];
int maxn = -1, l = 0, r = 0;
/*
maxn: 指最大和
l, r: 指最大连续子序列的头和尾
*/
for(int i = 0; i < K; i++){
int tmp;
scanf("%d", &tmp);
if(i == 0) //特判
f[i] = tmp, L[i] = i;
else{
if(f[i-1] >= 0) //这里不能写大于
f[i] = f[i-1] + tmp, L[i] = L[i-1];
else
f[i] = tmp, L[i] = i;
}
if(maxn < f[i]){ //这里不能写小于等于,因为题目要求l与r最小
maxn = f[i];
l = L[i], r = i;
}
}
if(maxn < 0) maxn = 0; //特判
printf("%d %d %d\n", maxn, l, r);
}
return 0;
}