首页 > ACM题库 > HDU-杭电 > HDU 3421-Max Sum II[解题报告]HOJ
2014
03-23

HDU 3421-Max Sum II[解题报告]HOJ

Max Sum II

问题描述 :

Given a sequence a[1],a[2],a[3]……a[n], you can cut the sequence into one or more consecutive sub-sequences as you want, for example, you can cut them into (a[1]…a[j]), (a[k]…a[l]), (a[m]…a[n]),1≤j<k≤l<m≤n. Your job is to make the maximum sum using the least number of consecutive sub-sequences. For example, given (6,-1,0, -2, 3), the max sum in this sequence is 9, the number of sub-sequences is 2 not 3, they are(6), (3).

输入:

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=1000000), then N integers followed(all the integers are between -1000 and 1000).

输出:

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=1000000), then N integers followed(all the integers are between -1000 and 1000).

样例输入:

2
2 6 -5
5 6 -1 0 -2 3

样例输出:

Case 1:
1 6

Case 2:
2 9

/*
hdu 3421 Max Sum II 读不懂题的伤不起啊
题意:吧一串数字 分成几串,串数尽量少(能用0链接起来的两串就用0链接起来),使其中几串的和最大
*/

#include<stdio.h>
__int64 he;
int main()
{
	int t,n,i,ret,qian,j,dang;
	scanf("%d",&t);
	for(i=1;i<=t;)
	{
		he=0;
		scanf("%d",&n);
		qian=-1;
		ret=0;
		int ji=0;
		for(j=1;j<=n;j++)
		{
			scanf("%d",&dang);
			if(dang>0) he+=dang;
			if(ji)
			{
				if(dang<0)
				{
					ji=0;
				}
			}else
			{
				if(dang==0)
				{
					
				}else if(dang>0)
				{
					ji=1;
					ret++;
				}
			}
		}
		if(i!=1)
			printf("\n");
		printf("Case %d:\n",i++);
		printf("%d %I64d\n",ret,he);
	}
	return 0;
}

参考:http://blog.csdn.net/qq172108805/article/details/8759486


  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。