最大前缀和C++

//给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。

#include<iostream>

using namespace std;

const int N=2e5+10;//注意全局常量必须在前面添加const

int a[N];//序列a定义成全局变量

int sum[N];

int main(){

int n;//长度n

cin>>n;

for(int i=1;i<=n;i++){//注意此处i从1开始，下面才可以使用pre=sum[0]

cin>>a[i],sum[i]=sum[i-1]+a[i];//输入a[i]的值，后面是前缀和的定义 sum[1]=sum[0]+a[1],a[1]=sum[1],sum[0]=0

}

int pre=sum[0];//pre初始化

int ans=-2e5;

for(int i=1;i<=n;i++){// 要求最大前缀和，就是求第i个数为结尾的最大子区间和 的意思：假设j到i是最大子区间，用前缀和的方法解决就是用i的和减去j-1的和，即sum[i]-sum[j-1]=sum[j,i] 那么要让sum[j,i]最大，就是让sum[i]最大，sum[j-1]最小

int temp=sum[i]-pre;//temp就是记录所有的sum[j,i]值 一直算 选出一个最大的传给ans

ans=max(ans,temp);//ans就是sum[i]

pre=min(pre,sum[i]);//pre就是sum[j-1] 

}

cout<<ans<<endl;

}