洛谷题目链接
题目赋值出来格式有问题,所以我就只放题目链接了
下面为ac代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=+;
ll a[maxn];//存放输入的数据
ll f[maxn];//用来递推
int main()
{
ll n;
cin>>n;
for(ll i=;i<=n;i++)
scanf("%lld",&a[i]);//输入数据 for(ll i=;i<=n;i++)
{
f[i]=max(a[i],a[i]+f[i-]);
} ll ans=f[];//先给ans赋初值为f[i] for(ll i=;i<=n;i++)//这里的意思是让ans等于f[1~n]中最大的
if(f[i]>ans)
ans=f[i]; cout<<ans<<endl; }
点击加号展开代码
文字讲解(代码中也有部分注释):
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<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=+;
ll a[maxn];//存放输入的数据
ll f[maxn];//用来递推
int main()
{
ll n;
cin>>n;
for(ll i=;i<=n;i++)
scanf("%lld",&a[i]);//输入数据 for(ll i=;i<=n;i++)
{
f[i]=max(a[i],a[i]+f[i-]);
} ll ans=f[];//先给ans赋初值为f[i] for(ll i=;i<=n;i++)//这里的意思是让ans等于f[1~n]中最大的
if(f[i]>ans)
ans=f[i]; cout<<ans<<endl; }