题解 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);//输出
}
```