题目赋值出来格式有问题,所以我就只放题目链接了

 下面为ac代码

#include
      
       #define ll long longusing namespace std;const ll maxn=200000+10;ll a[maxn];//存放输入的数据ll f[maxn];//用来递推int main(){    ll n;    cin>>n;    for(ll i=1;i<=n;i++)        scanf("%lld",&a[i]);//输入数据    for(ll i=1;i<=n;i++)    {        f[i]=max(a[i],a[i]+f[i-1]);    }    ll ans=f[1];//先给ans赋初值为f[i]    for(ll i=2;i<=n;i++)//这里的意思是让ans等于f[1~n]中最大的        if(f[i]>ans)            ans=f[i];    cout<
       
        <
       
      

文字讲解(代码中也有部分注释):

f[i]数组的意义是以a[i]为末尾的序列中最大的总和

比如说序列1 3 4

那么f[1]=1,f[2]=1+3=4,f[3]=1+3+4=8

然后如果从左往后递推,也就是f[i],i从1~n

f[i],可以等于a[i],也可以等于f[i-1]+a[i]

这两个要看谁大,所以要用max函数,具体的递推方程就是:

f[i]=max(a[i],a[i]+f[i-1])

比如说当f[i-1]=4,a[i]=-1,那么f[i]就肯定选和f[i-1]合并比较好

那么如果f[i-1]=-1,a[i]=4,此时f[i]=a[i]能保证f[i]是以a[i]为末尾的序列中最大的总和

类似的栗子还有好多,可以自己举栗子看看

 

接下来推荐一道类似的知识点题目:

最长不下降子序列

 再贴一次代码

#include
     
      #define ll long longusing namespace std;const ll maxn=200000+10;ll a[maxn];//存放输入的数据ll f[maxn];//用来递推int main(){    ll n;    cin>>n;    for(ll i=1;i<=n;i++)        scanf("%lld",&a[i]);//输入数据    for(ll i=1;i<=n;i++)    {        f[i]=max(a[i],a[i]+f[i-1]);    }    ll ans=f[1];//先给ans赋初值为f[i]    for(ll i=2;i<=n;i++)//这里的意思是让ans等于f[1~n]中最大的        if(f[i]>ans)            ans=f[i];    cout<
      
       <