51nod 1050 循环数组最大子段和

题目链接:51nod 1050 循环数组最大子段和

 #include<stdio.h>
#include<algorithm>
using namespace std;
const int N = ;
long long a[N];
int main(){
int n, i;
long long ma_ed, ans, sum = ;
scanf("%d", &n);
for(i = ; i <= n; ++i){
scanf("%I64d", &a[i]);
sum += a[i];
}
ma_ed = a[];
ans = max(0LL, a[]);
for(i = ; i <= n; ++i){//1~n求最大子段和
if(ma_ed > )
ma_ed += a[i];
else
ma_ed = a[i];
ans = max(ma_ed, ans);
}
long long mi_ed = a[], s = a[];
//最大字段和首尾相接情况
for(i = ; i <= n; ++i){
if(mi_ed < )
mi_ed += a[i];
else
mi_ed = a[i];
s = min(mi_ed, s);
}
//首尾相接时,答案为序列数的总和 与 其中数相加最小的和(负值) 之差
printf("%I64d\n", max(ans, sum - s));
return ;
}
上一篇:kmp模式串匹配


下一篇:DotNetCore跨平台~组件化时代来了