HDU/1003

摘要

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

• 来自寒假练习：Only a signing tool ! D题
• 原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1003

题意

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

题解

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

即记=a[1]+a[2]+...+a[i]，那么

• 显然对于每一个确定的j，是一定的，以他为结尾的最长子序列可以通过计算-min{}(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"); } }