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
解题思路
这么简单的 DP 题，却做了这么久才做出来，啥也不说了( >﹏<。)～呜呜呜……
解题代码
//
// main.cpp
// Max Sum
//
// Created by Yeah on 13-10-15.
// Copyright (c) 2013年 Yeah. All rights reserved.
//
#include <iostream>
usingnamespacestd;#define MAX_N 100001
intnums[MAX_N];intmain(){unsignedintT(0);cin>>T;for(intCase_Num(1);Case_Num<=T;Case_Num++){unsignedintN(0);cin>>N;for(inti(1);i<=N;++i){cin>>nums[i];}intMax(-100000001),Sum(0);intStart_Pos(1),End_Pos(0);for(inti(1),temp_Start(1);i<=N;++i){Sum+=nums[i];if(Sum>Max){Max=Sum;Start_Pos=temp_Start;End_Pos=i;}if(Sum<0){Sum=0;temp_Start=i+1;}}cout<<"Case "<<Case_Num<<':'<<endl;cout<<Max<<' '<<Start_Pos<<' '<<End_Pos<<endl;if(Case_Num!=T){cout<<endl;}}return0;}