[1593] Max Sum
- 时间限制: 1000 ms 内存限制: 65535 K
- 问题描述
-
You must learn the classic Dynamic Programming problems about “Max Sum of the
Subsegment ”. Now you are given a cicle ring which contains n ( 1≤n≤100000 )integers
a1, a2, ... , an with clockwise order. I want to know the “Max Sum of the Subsegment” in the ring.
- 输入
-
Input starts with an integer T( T ≤50 ) denoting the test cases.
For each test case, the first line will contain an integer n, then n signed 32 bits integers will
be followed in the next line. - 输出
-
For each test case, print the case number and your answer.
- 样例输入
-
2 4 1 -1 -2 10 5 -3 4 1 -2 3 4 -1 -1 -1 -1
- 样例输出
-
Case 1: 11 Case 2: 6 Case 3: -1
- 提示
-
In the first sample, the max sum is 11, which equals 10 + 1(nth and 1th is adjacent)
- 来源
-
Alex@NBUT
- 操作
-
