这题依旧是昨天做的一批中的WA一员，WA的自闭，虽然感觉写HDOJ蛮好玩的，WA的......难受一匹是吧....一样的跪求大神指正
思路也很简单就是动态规划，哨兵往下总和大于原来的sum，sunm就交换并且拿到哨兵的index，如果总和>=0有增加的可能就继续，如果总和<0就pass,从下一位继续.....
/* 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 1 10 -5 -6 3 2 1 -7 6 3 -10 8 答案：9 7 8 1 10 9 -6 -7 3 2 1 -1 -1 -1 9 答案：12 4 10 */ # include <iostream> # define Num 100001 using namespace std; int a[Num]; void out(int time,int sum,int s,int e) { cout << "Case " << time << ":" << endl; cout << sum << " " << s << " " << e << endl; } int addMax(int*a,int n, int *startIndex1, int*endIndex1) { *startIndex1 = *endIndex1 = 0;//重置0位置 int sum = -999; int temp_Sum = 0; int tsindex, teindex; tsindex = teindex = 1; for (int i = 0; i < n; ++i) { temp_Sum = temp_Sum + a[i];//加上当前数字 if (temp_Sum >= 0) {//有希望 teindex = i+1;//如果有上升趋势那么临时end上去 if (temp_Sum > sum) { sum = temp_Sum; *startIndex1 = tsindex; *endIndex1 = teindex; } } else {//已经负数没上升趋势了 tsindex = i + 2;//当前坐标为 i 但是在1为开头是 i+1 所以下一个是 i+2 teindex =tsindex;//当前坐标 i 一定是大负数 temp_Sum = 0; } } return sum; } int main(void) { int n;//次数 int N;//每次个数 int startIndex=1, endIndex=1; int sum = 0; cin >> n;//次数 if (n >= 1 && n <= 20) { for (int j = 0; j < n; ++j) { cin >> N;//确认录入数组个数 if (N >= Num)//此行加上就不会出先运行时错误(真的烦) return 0; for (int i = 0; i < N; ++i) { cin >> a[i]; }//对数组进行输入 //对数组进行动态规划统计最大值，起始位置和终止位置 sum = addMax(a, N, &startIndex, &endIndex); out(j + 1, sum, startIndex, endIndex); if (j != n - 1) cout << endl; } } else return 0; system("pause"); return 0; }哪里错了.......
