Max Sum

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 20   Accepted Submission(s) : 8

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

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.

Input

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<=100000), then N integers followed(all the integers are between -1000 and 1000).

Output

For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

Sample Input

2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

Sample Output

Case 1:
14 1 4

Case 2:
7 1 6

Author

Ignatius.L 


思路：
题意就是给出一串数，让你求出这串数中最大的连续的数的和。动态规划问题，就是看加的时候能不能使它变得更大。用maxn来保存最大值,pos1用来保存最大连续和的起始位置，pos2保存终止位置。然后用cnt1代表不断变化的初始cnt2表示不断变化的末尾位置，如果maxn被更新，则把当前的cnt1赋值给pos1，末尾位置赋值给pos2。然后主要WA的一点就是比如说测试数据是 1  3 -3 -2 -1。一开始把maxn的初始值设的-1太大了，应该设到-10000，就过了。



代码： 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

int main()
{
	freopen("in.txt","r",stdin);
	int t;
	scanf("%d",&t);
	for(int k=1;k<=t;k++)
	{
		int n;
		scanf("%d",&n);
		int sum=0;
		int num;
		int maxn=-10000;
		int pos1=-1,pos2=0;
		int cnt1=-1,cnt2=0;
		int fushu=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&num);
			sum+=num;
			if(pos1==-1&&num<0)
			{
				fushu=num;
				pos1=i;
				cnt1=i;
			}
			if(pos1==-1&&num>=0)
			{
				pos1=i;
				cnt1=i;
				cnt2=i;
			}
			if(sum>maxn)
			{
				maxn=sum;
				cnt2=i;
				pos1=cnt1;
				pos2=cnt2;
			}
			if(sum<0)
			{
				cnt1=i+1;
				sum=0;
			}	
		}
		printf("Case %d:\n",k);
		if(pos1==-1)printf("%d %d %d\n",fushu,1,1);
    	else 	printf("%d %d %d\n",maxn,pos1,pos2);
		if(k!=t)		printf("\n");
	}
	return 0;
}