题解 | #最大序列和#

#include <stdio.h>

#define N 1000000
#define MIN -1000000

int main() {
    int dp[N];  //存放加上当前元素的最大子序列和
    int num[N]={0};  //存放序列元素
    int n;
    int max;  //记录最大子序列和
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%d",&num[i]);
        }
        dp[0]=num[0];
        max=MIN;
        for(int i=1;i<n;i++){
            dp[i]=(num[i])>(num[i]+dp[i-1])?(num[i]):(num[i]+dp[i-1]);  //如果当前元素前一个的最大子序列和大于0则加上，否则不加
            if(dp[i]>max)
                max=dp[i];
        }
        printf("%d\n",max);
    }
    return 0;
}