前缀和，连续子数组和最大

动态规划没想出来，想出来一个前缀和找最大区间和的方法；
第二个for循环里边记录已遍历点之前的最小值，方便后续做差寻找最大区间和；
注意第二个for循环从0开始(否则类似1 2 3 4 5 6判断不全)，最后特判n==0输出；

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9,maxn=1e7;
int n,num[maxn],sum[maxn];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){//统计前缀和
        cin>>num[i];
        sum[i]=sum[i-1]+num[i];
    }
    int minN=inf,ans=0;
    for(int i=0;i<=n;i++){//寻找最大区间和；
        ans=max(ans,sum[i]-minN);
        minN=min(minN,sum[i]);
    }
    if(n>1)cout<<ans<<endl;//输出答案；
    else cout<<num[1]<<endl;
    return 0;
}