Description
When there is a sequence { -1, 2, 5, -3, 9, 8, -4, -5, 10, -11 }, the sum of all elements of this sequence is 10.
However, if you calculate the sum of elements from the 2nd to the 9th, it is 22. In this sequence, the subsequence from the 2nd to the 9th is the maximum subsequence of this sequence.
When a sequence consisting of N elements is input, write a program that calculates the subsequence of this sequence whose sum is the maximum.
Input
First, the number of test cases T (1 <= T <= 100) is input. Then, the number of elements N is input as many as the number of T, and N elements e[i] are input. (3 <= N <= 500, -1,000 <= e[i] <= 1,000)
Output
For each test case, output the sum of the subsequence of the sequence whose sum is the maximum line by line.
3
4
1 -1 1 2
5
1 -2 3 -4 5
10
-1 2 5 -3 9 8 -4 -5 10 -11