【HDU1003】Max Sum(最大子序列和)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 09 月 15 日

Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
题目说的不清楚,按照自己弄的一些数据测试出最终要的结果是:最长最大子序列和,如果有多个结果输出第一组。题目中没有体现出 “最长” 这一字眼。

另外对这次不太明白的可以看 【POJ1050】To the Max (动态规划、最大字串和、最大子矩阵和)||NYOJ44 ||NYOJ104

#include<cstdio>
#include<iostream>
#include<climits>
using namespace std;
const int MAX=100010;
int a[MAX]={0};
int main()
{
	freopen("1.txt","r",stdin);
	int n,m,maxsum,loop,first=0;
	scanf("%d",&n);
	loop=n;
	while(n--)
	{
		if(first!=0) puts("");
		printf("Case %d:\n",loop-n);
		first=1;
		maxsum=-INT_MAX;
		scanf("%d",&m);
		int beg=1,end=1,temp=1;
		for(int i=1;i<=m;++i)
		{
			scanf("%d",&a[i]);
			if(a[i-1]<0) temp=i;
			if(a[i-1]>0) a[i]+=a[i-1];
			if(a[i]>=maxsum) {maxsum=a[i];beg=temp;end=i;}
		}
		printf("%d %d %d\n",maxsum,beg,end);
	}
}

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期六, 2017 年 10 月 21 日