题解 P1115 【最大子段和】

Citus_Neru_index · 2018-10-04 19:20:52 · 题解

这题就是比较基础的最大子段和的DP，其实这题我的想法很简单，就是用全是正数的状态转移方程，然后加个记录最大值，但是这么写，只能80分 80分的code：

#include<cstdio>
#include<iostream>
using namespace std;
int opt[200005],num[200005],maxx=-99999;
int main()
{
    int N,i;
    scanf("%d",&N);
    for(i=1;i<=N;i++)
    scanf("%d",&num[i]);
    for(i=1;i<=N;i++)
    {
        if(opt[i]<opt[i-1]+num[i])opt[i]=opt[i-1]+num[i];
        if(opt[i]>maxx)maxx=opt[i];
    }
    printf("%d",maxx);
    return 0;

}

然后我就很懵逼，然后看讨论，发现入过是3，-1，-2，-3之类的数据（即全是复数）答案就会是0，那么怎么改？opt数组不好改，那么这是，我就想出了一个方法，先上代码 100分code：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int opt[200005],num[200005],maxx=-99999;
int main()
{
    int N,i;
    scanf("%d",&N);
    for(i=1;i<=N;i++)
    scanf("%d",&num[i]);
    for(i=1;i<=N;i++)
    {
        if(opt[i]<opt[i-1]+num[i])opt[i]=opt[i-1]+num[i];
        if(opt[i]>maxx)maxx=opt[i];
    }
    if(maxx==0)
    {
        sort(num,num+N+1);
        printf("%d",num[N-1]);
        return 0;
    }
    printf("%d",maxx);
    return 0;
}

如果全是负数的话，那么肯定子段数为一且那个数最大，所以加个sort就可以了，找最大值。