1007 Maximum Subsequence Sum (25

简单动态规划。
以为尾的序列的最大序列和


迭代更新的同时顺便用一个数组记录那些构成最大序列和的序列的左端点。

#include<cstdio>
using namespace std;

const int MAXN=1e4;
int a[MAXN],dp[MAXN],l[MAXN];

int main(void) {
//    freopen("in.txt","r",stdin);
    int N;
    scanf("%d",&N);
    int r,ans=-1;
    bool ok=false;
    for(int i=0;i<N;i++){
        scanf("%d",&a[i]);
        if(a[i]>=0) ok=true;
        if(i==0){
            dp[i]=a[i];
            l[i]=i;
        }
        else{
            if(dp[i-1]+a[i]>a[i]){
                dp[i]=dp[i-1]+a[i];
                l[i]=l[i-1];
            }
            else{
                dp[i]=a[i];
                l[i]=i;
            }
        }
        if(ans==-1 || dp[i]>ans){
            ans=dp[i];
            r=i;
        }
    }
    if(ok==false){
        printf("0 %d %d\n",a[0],a[N-1]);
        return 0;
    }
    printf("%d %d %d\n",ans,a[l[r]],a[r]);
    return 0;
}

/*
Sample Input:
10
-10 1 2 3 4 -5 -23 3 7 -21

Sample Output:
10 1 4
*/