POJ 2479（动态规划·多段最大子序列求和）

题目链接：http://poj.org/problem?id=2479

Description

Given a set of n integers: A={a1, a2,…, an}, we define a function d(A) as below:

Your task is to calculate d(A).

Input

输入包含最多30个测试用例。测试用例的数量（T）由输入的第一行给出。
每个测试用例包含两行数据。
第一行是一个整数n（2≤n≤5×1e4）。
第二行包含n个整数a₁,a₂,…,aₙ。（|a_i| ≤ 1e⁴）
每个测试用例后面都留有一个空白行。

Output

For every test case, output precisely a single line. Each output must incorporate the integer d(A).

Sample Input

1

10
1 -1 2 2 3 -3 4 -4 5 -5

Sample Output

13

Hint

In the sample, we choose {2,2,3,-3,4} and {5}, then we can get th