濮阳新闻今日头条最新_湖北网站建站系统哪家好_搜索引擎费用_百度知道app官方下载

和之前的顺序一下

step1:

我们先确定状态表示 f[i]表示以i为终点的最大子段和

step2:确定状态表示方程

f[i]=f[i-1]+a[i]，仅仅是这样吗？no absolutely not  

我们假如以i-1为终点的最大字段和是负无穷，而a[i]是一个正数，那么 f[i-1]+a[i]肯定是比a[i]本身要小的，

所以我们真实的状态方程应该是f[i]=max(a[i],a[i]+f[i-1])

step3；初始化

我们数组下标从1开始，那么初始化f[1] 的时候 f[1]应该等于a[i] f[i-1]的值不应该影响最终结果

所以刚开始我们数组要初始化成0

为什么从下标1开始，这是为了防止越界

#include <iostream>
using namespace std;
const int N = 2e5+10;
typedef long long LL;
LL f[N];
LL a[N];
LL n;
int main()
{cin >> n;for(LL i = 1;i<=n;i++){cin >> a[i];}LL ret = -1e9;for(LL i = 1;i<=n;i++){f[i] = max(f[i-1]+a[i],a[i]);ret = max(f[i],ret);}cout << ret << endl;return 0;
}

当然我们是可以对空间做一些优化的，比如说，我们不必开一个a[N]数组，我们有一个f[N]数组就足够了，我们用一个临时变量输入n次代表每个数就行了

#include <iostream>
using namespace std;
const int N = 2e5+10;
typedef long long LL;
LL f[N];
LL a[N];
LL n;
int main()
{LL ret = -1e9;cin >> n;LL x;for(LL i = 1;i<=n;i++){cin >> x;f[i] = max(f[i-1]+x,x);ret = max(f[i],ret); }cout << ret << endl;return 0;
}