题解 | #最大序列和#

简单DP

思路：统计以s[i]结尾的最大子序列和ans[i]

• 关键找到递归关系：
• ans[i]： s[i]结尾的最大子序列分为2类：是/否包含s[i-1]
• ①不包含 前面序列对其没有贡献:ans[i]=s[i]
• ②包含 前面序列对其有贡献:ans[i]=ans[i-1]+s[i]

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn=1000001;
const long long INF=0xffffffffffffffff;
long long s[maxn];//序列
long long ans[maxn];//以s[i]结尾的最大子序列和

long long  maxsequence(int n){
    long long maxans=INF;//最大序列和
    ans[0]=s[0];//起始
    for(int i=1;i<n;i++){
        ans[i]=max(s[i]+ans[i-1],s[i]);//递推
        maxans=max(maxans,ans[i]);//更新最大序列和
    }
    return maxans;
}

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        fill(ans,ans+n,INF);//初始化
        for(int i=0;i<n;i++)scanf("%lld",&s[i]);
        printf("%lld\n",maxsequence(n));
    }
    return 0;
}