前缀和

P1115 最大子段和

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 const int N=2*100010;
 5 int n,a;//保存原数列
 6 long long b[N]; //保存a的前缀和
 7 int main() { 
 8     scanf("%d",&n);
 9     for(int i=1; i<=n; i++) {
10         scanf("%d",&a);
11         b[i]=a+b[i-1];
12     }
13     long long ans=b[1];//定义答案初始值 
14     long long mmin=0;//定义前n项和最小值 
15     for(int i=1; i<=n; i++) {
16         ans=max(ans,b[i]-mmin);//连续区间至少要有一个数 
17         mmin=min(mmin,b[i]);
18     }
19     printf("%lld",ans);
20     return 0;
21 }