查看HDU/1003的源代码 ←HDU/1003

[[分类:贪心]]
==摘要==
{{信息题|Max Sum|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}68572#problem/D|1|100|time=2015-02-06 10:58:51}}
*来自寒假练习：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=68572 Only a signing tool !] D题
*原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1003
==题意==
给一串序列，求子序列使得其和最大。
==题解==
*瞄了一眼N的范围，发现只能写O(n)的算法，基本就是贪心了。我们都知道求一段a[i]~a[j]的和可以通过求前缀和求得：
即记<m>s_i</m>=a[1]+a[2]+...+a[i]，那么<m>sum_{itoj}=s_j-s_{i-1}</m>
*显然对于每一个确定的j，<m>s_j</m>是一定的，以他为结尾的最长子序列可以通过计算<m>s_j</m>-max{<m>s_i</m>}(i<j)来得到，而这是可以之前边录入边处理的。
*最后将每一个j所求得的最长子序列求个最大值就好了。详见代码。
==代码==
{{折叠|1003.cpp代码已折叠
|<pre>
#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");
    }
}
</pre>
|code1003}}