题解 P1115 【最大子段和】

一道标准的练手dp好题。

下面提出标准最大子段和做法：

边读边做。

now代表目前加起来是多少。

读一个a now加一次。

如果now>ans ans=now

如果now<0 正常情况下这种方法不合理，但。。。。

有测试点#2.

全是负数！这个特殊情况一定要考虑！

所以 代码来了：

#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);//输出
}//只要你懂，代码其实可以很短。（自认为我的代码最短）