又来水题解了
** 题目传送门**
又是一道经典的 dp
实际上这题也没有大家想的辣么难啊……
首先还是从不同的算法分析吧：
- 暴力
爆搜这代码简单直白。实际上我们需要枚举l和r，然后计算[l,r]的元素和就阔以了。
** **
所以我们需要一个更高效的算法。
首先，我们现在纸上写一写：
** 2、-4、3、-1、2、-4、3。答案4（选3、-1、2）**
那么是怎么推出来的呢？
首先看到第一个数，是。
后面是，所以如果是答案的一部分，那么一定也要加上去（答案就增加了）
随后是。
如果把前面的和加上去，结果是。这个时候反而比原来的要小了。所以如果答案含有，就一定不会加上前面的和。
下一个数是。这个数加上前面的之后增加了数值（变成了），所以如果答案有，辣么绝对还有前面的。
接下来是，如果加上前面的序列，辣么它的值变为。比原先增加了。
然后是，如果把加上前面的序列，结果会变成，比原先的大，所以如果是答案的一部分，那么前面的三个数也一定是答案的一部分。
最后一个数，也就是，如果将加上前面的序列，结果变成了。
最后我们来看一看刚推导的结果，发现是我们可以得出的最大和。
故输出4
所以说了这么多 （还用了这么多Markdown改颜色） ，最终的结果是什么呢？
在处理的过程中计算有效序列的所有元素之和。
最后取最大值即可。
（如果还有人不懂，我也只能贴代码了）
#include<bits/stdc++.h>
using namespace std;
int n,a[200020],b[200020],i,ans=-2147483647;
int main(){
cin>>n;
for(i=1;i<=n;i++){
cin>>a[i];
if(i<2) b[i]=a[i];
else b[i]=max(a[i],b[i-1]+a[i]);
ans=max(ans,b[i]);
}
cout<<ans;
return 0;
}
这个代码之所以我没有加注释，是因为……
我们来看一眼代码：
- 输入a[i]
- 给b[i]赋值
- 给ans赋值
全程中 a 数组是没有意义的，也就是说，它可以被一个变量代替。
然后再来看一眼 b 数组 （b 数组：你不要过来啊）
全程我们只用到了 b[i] 元素和 b[i-1] 元素
是不是闻到了滚动数组的气息？
最终我们可以得出
#include<bits/stdc++.h>
using namespace std;
int n,a,b[2],i,ans=-2147483647;
// b数组用于存储序列和。
int main(){
cin>>n;
for(i=1;i<=n;i++){
cin>>a;//将数组优化为一个变量
if(i<2) b[1]=a;
else b[i&1]=max(a,b[!(i&1)]+a);//前面推导的步骤，配合滚动数组食用
ans=max(ans,b[i&1]);//更新答案
}
cout<<ans;
return 0;
/*
*
* 这里说一下代码里的位运算,&1 可以看做是 %2 。
* 而加上感叹号就是 0变1 , 1变0
*
*/
}
最后的效果还是很明显的，从 2.13MB 变成了 820KB
我也不知道最后写啥就让一个分割线结束这篇题解吧QAQ
update:修改了推导过程中一个bug，完善过程
