题目内容

P1115

大意:给出一段序列,求其中最大的连续非空子段和

解题思路

一般这种鬼东西都是dp。

注意到要求的子段和是连续的,所以这题的性质很显然。

f(x)为从1x的最大子段和,则当面临一个新的x时,要么将这个x加进原来的最大子段和,要么重新开一个字段,因此方程式是:

f(x)=\max(f(x-1)+a_x,a_x)

其中a_x为序列的第x项。

但是统计到最后的f(n)不一定是最大子段和,所以需要重新统计一遍。

当然我使用的是设置一个答案变量,统计这一过程中最大的f(x),同时a_i也是没必要存下来的,可以每一次读入的时候就进行处理,这样还可以优化一部分常数。

代码如下:

#include <cstdio>

const int maxn=2e5+5;

int f[maxn],n,ans=-0x3f3f3f3f;

int max(int a,int b)//手写max会更快
{
    return a>b?a:b;
}

int main()
{
    scanf("%d",&n);
    f[0]=0;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        f[i]=max(f[i-1]+x,x);
        ans=max(f[i],ans);
    }
    printf("%d\n",ans);
    return 0;
}
最后修改日期:2020年2月4日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。