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.
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).
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.
这题和 HDU-1231 类似，但是我不知道为什么按那个模板来进行改写会有答案错误，所以就多改了一点内容。 参考代码：
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <stack> #include <queue> #include <map> #include <set> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; #define ll long long #define clean(arrays) memset(arrays, 0, sizeof(arrays)) int main() { int t, a[100100]; scanf ("%d", &t); for (int i = 1; i <= t; i++) { clean (a); int n, sum = -11234, index = 0, ans = 1, first = 1, finally = 1; scanf ("%d", &n); for (int j = 1; j <= n; j++) scanf("%d", &a[j]); for (int k = 1; k <= n; k++) { index += a[k]; if (index > sum) //这两个 if 不能调换位置 { sum = index; first = ans; finally = k; } if (index < 0) { index = 0; //这里 index 为 0 ，因为循环开始index要加上a[k] ans = k + 1; } } printf ("Case %d:\n%d %d %d\n", i, sum, first, finally); if (i < t) printf ("\n"); } return 0; }