Max Water Saved (Maximum Contiguous Subarray Sum)

You are given several test cases. For each test case, you are given an array of integers that represent the water requirements of consecutive crops. The task is to determine the maximum amount of water that can be saved, which is equivalent to finding the maximum sum of a contiguous subarray. This is a classic problem that can be solved by Kadane's algorithm.

Formally, given an array \(a_1, a_2, \ldots, a_N\), you need to find the maximum value of \(\sum_{i=l}^{r} a_i\) for some \(1 \leq l \leq r \leq N\).

inputFormat

The input is read from standard input and has the following format:

T
N_1
a11 a12 ... a1N1
N_2
a21 a22 ... a2N2
...
N_T
aT1 aT2 ... aTNT

Where \(T\) is the number of test cases. For each test case, the first line contains an integer \(N\) (the number of crops) followed by a line with \(N\) integers representing the water requirements. The requirements may be negative, representing a loss of water savings.

outputFormat

For each test case, output a single line containing the maximum contiguous subarray sum (i.e. the maximum water that can be saved).

## sample

2
5
1 2 3 4 5
3
10 20 30

15
60

</p>