（以“分类:贪心 ==摘要== {{信息题|Max Sum|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}68572#problem/D|1|100|time=2015-02-06 10:58:51}} *来自...”为内容创建页面） |
小 （→题解： min） |
||
| 第9行： | 第9行： | ||
*瞄了一眼N的范围，发现只能写O(n)的算法，基本就是贪心了。我们都知道求一段a[i]~a[j]的和可以通过求前缀和求得： | *瞄了一眼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> | 即记<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>- | + | *显然对于每一个确定的j，<m>s_j</m>是一定的，以他为结尾的最长子序列可以通过计算<m>s_j</m>-min{<m>s_i</m>}(i<j)来得到，而这是可以之前边录入边处理的。 |
*最后将每一个j所求得的最长子序列求个最大值就好了。详见代码。 | *最后将每一个j所求得的最长子序列求个最大值就好了。详见代码。 | ||
| + | |||
==代码== | ==代码== | ||
{{折叠|1003.cpp代码已折叠 | {{折叠|1003.cpp代码已折叠 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| Max Sum | ★☆☆☆☆ | 答案正确 | 100 | 2015-02-06 10:58:51 | 无 |
给一串序列，求子序列使得其和最大。
即记=a[1]+a[2]+...+a[i]，那么
| 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");
}
}
|
CloudLunar