洛谷 1115_最大子段和_dp?

发布于 2019-05-07  989 次阅读


题目描述

给出一段序列,选出其中连续且非空的一段使得这段和最大。


思路

如果加上这个数不小于某个数就加,否则清0
这里有负数,所以这个玄学系数就随便yy一下就可以了

O(n)


#include 
int f[200001];
int main()
{
    int n,m;
    scanf("%d",&n);
    int ans=-200,max=0;
    for (int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        max+=x;
        if (max>ans) ans=max;
        if (max<=-200) max=0;
    }
    printf("%d\n",ans);
}
]]>