#599 Maximum Subarray Problem

Statement

Statement language

You are given a sequence $A=[A_1,A_2,\cdots,A_N]$ of length $N$ . Find the maximum value of

\sum_{i=l}^{r} A_i \qquad (1\leq l\leq r\leq N).

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each case, print the maximum value on its own line.

#	Score	Constraints
1	20	$N\leq500$ , and the sum of $N$ over all cases is at most $500$ .
2	30	$N\leq5000$ , and the sum of over all cases is at most .

Input

4
5
1 -2 3 4 -1
3
-5 -2 -7
4
0 0 0 0
4
1 2 3 4

Output