题解 | 最大子段和

#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
scanf("%d",&n);
vector<int>a(n+3);
vector<long long>dp(n+3);
long long nnc=-100000001;
for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    if(nnc<a[i]){
        nnc=a[i];
    }
    dp[i]=0;
}

if(a[1]>=0){
    dp[1]=a[1];
}
long long mcx=-100000001;

for(int i=2;i<=n;i++){
    long long cand=dp[i-1]+a[i];
    if(cand>dp[i]){
        dp[i]=cand;
    }
    if(mcx<dp[i]){
        mcx=dp[i];
    }
}
if(nnc<=0&&mcx==0){
    printf("%lld",nnc);
    return 0;
}
printf("%lld",mcx);


}

结合dp思想，将大问题变成了小问题，同时在结合前缀和思想