摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 需要注意
Max Sum ★☆☆☆☆ 答案正确 100 2015-02-06 10:58:51

题意

给一串序列,求子序列使得其和最大。

题解

  • 瞄了一眼N的范围,发现只能写O(n)的算法,基本就是贪心了。我们都知道求一段a[i]~a[j]的和可以通过求前缀和求得:

即记s_i=a[1]+a[2]+...+a[i],那么sum_{itoj}=s_j-s_{i-1}

  • 显然对于每一个确定的j,s_j是一定的,以他为结尾的最长子序列可以通过计算s_j-max{s_i}(i<j)来得到,而这是可以之前边录入边处理的。
  • 最后将每一个j所求得的最长子序列求个最大值就好了。详见代码。

代码

1003.cpp代码已折叠
展开折叠内容
#include<cstdio>
#include<cstring>
#include<climits>
#define _for(i,n) for(int i=1;i<=n;++i)
int sum[120000]={},a[120000]={};
void Work()
{
    sum[0]=0;
    int n,ans=INT_MIN,ansX,ansY,sumMin=0,sumMinN=0;
    scanf("%d",&n);
    _for(i,n)
    {
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
        if(sum[i]-sumMin>ans)
        {
            ans=sum[i]-sumMin;
            ansX=sumMinN+1;
            ansY=i;
        }
        if(sumMin>sum[i])
        {
            sumMin=sum[i];
            sumMinN=i;
        }
    }
    printf("%d %d %d\n",ans,ansX,ansY);
}
int main()
{
    int T;
    scanf("%d",&T);
    _for(i,T)
    {
        printf("Case %d:\n",i);
        Work();
        if(i!=T)
            printf("\n");
    }
}

著作权声明[编辑]

关于[编辑]