杭电ACM题1003

杭电题1003

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



   这题跟我有仇哈。。。。

          
#include "iostream"
using namespace std ;

int main()
{
	int a[1003];//存储输入的一些数
	int str[1003];//存储依次计算得到的和
	int start[1003];//存储序列和种最大值的最先开始元素序号
	int t,n;
	int num=1;
	cin>>t;
	while (t--)//case的次数
	{
		cin>>n;//输入n个数
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		str[1]=a[1];
		start[1]=1;
		for (int j =2;j<= n;j++)
		{
			if (str[j-1]>=0)//元素数和大于0则继续看下一位
			{
				str[j]=str[j-1]+a[j];
				start[j]=start[j-1];
			}else{//小于0从写一个元素记录开始
				str[j]=a[j];
				start[j]=j;
			}
		}
		int max=str[1];
		int end=1;//随便初始化一下
		for ( int k = 0; k<=n; k++)//找到序列和中的最大值
		{
			if (str[k]>max)
			{
				max=str[k];
				end=k;
			}

		}
		cout<<"Case"<<" "<<num<<":"<<endl;
		num++;
		cout<<max<<" "<<start[end]<<" "<<end;
		if (t) cout<<endl;

	}
    return 0;
}

<span style="color:#000066;">跟着学习了，原来这样才能通过杭电的编辑器</span>
           
    
#include "iostream"
using namespace std ;

int main(){  
	int r = 0,l = 0,i= 0 ,j = 0,num =0,n,t=0;
	int sum = 0,max = 0; 
	int *a;
	cin>>n;
	while(n--){
		cin>>num;
		a = (int *)calloc(num,sizeof(int));  
		for(i = 0; i < num ;i ++)
			cin>>a[i];
		for( l = 0,r = 0,sum = 0,max = a[0],i = 0;i <num ;i ++)
		{
			for(sum = 0,j = i ;j <num ;j ++)
			{
				sum += a[j];
				if(sum > max){
					max = sum ;
					l = i;
					r = j;
				}
				if(sum < 0){
					i = j;
					sum =0;
					break;  
                    }  
                }  
            }  
		t++;
			cout<<"Case"<<" "<<t<<":"<<endl;
			cout<<max<<" "<<l+1<<" "<<r+1<<endl;
			if (n) cout<<endl;
		}
		system("pause");
        return 0;  
    }