题解 P1115 【最大子段和】
引领天下
2017-09-07 19:44:46
一道标准的练手 dp 好题。
下面提出标准最大子段和做法：
边读边做，$now$ 代表目前加起来是多少。
当读入一个 $a$ 时，$now$ 先直接加上 $a$，如果 $now>ans$，那么就用 $now$ 更新 $ans$。
如果 $now<0$，正常情况下应该直接舍弃，但。。。。
有测试点 #2。
全是负数！这个特殊情况一定要考虑！
所以，代码来了：
```cpp
#include <cstdio>//标准输入输出库
int main(void){
int n,a,ans=1<<31,now,c=1;//ans初值一定要给小一点（防#2)(int最大值是1<<31-1,所以1<<31直接跳负数
scanf ("%d",&n);//读入
while (n--){//既然边读边做，要n何用？
scanf ("%d",&a);//读入a
now+=a;//now加一下
if (now>ans)ans=now;//注意这句和下句的顺序！如果反过来，就只有80分了（臭不要脸的测试点#2）
//同时找到了最大值
if (now<0)now=0;//如果now小于0，这种方案肯定不可取，归0（屁股免打，下次再来）
}
printf ("%d",ans);//输出
}
```