题解 | #最大序列和#

#include <cstdio>
#include <iostream>

using namespace std;

const int MAX=1000000;

long long arr[MAX];
long long dp[MAX];

long long MAXSubSequence(int n){
    long long maxSum=0;
    
    for(int i=0;i<n;i++){
        if(i==0){
            dp[i]=arr[i];
        }else{
            dp[i]=max(arr[i],dp[i-1]+arr[i]);
        }
        maxSum=max(maxSum,dp[i]);
    }
    return maxSum;
}

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0){
            break;
        }
        for(int i=0;i<n;i++){
            scanf("%lld ",&arr[i]);
        }
        long long answer=MAXSubSequence(n);
        printf("%lld\n",answer);
    }
    return 0;
}