Maximum Subarray Sum

You are given T test cases. For each test case, you are provided with an integer N representing the number of elements in an array followed by N space-separated integers. Your task is to find the maximum sum of any contiguous subarray within the given array.

Hint: You can use Kadane's algorithm, which is based on the recurrence

$$max\_current = \max(a_i, max\_current + a_i)$$

and update the global maximum accordingly.

inputFormat

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

• The first line contains an integer T, the number of test cases.
• For each test case, the first line contains an integer N, the length of the sequence.
• If N > 0, the next line contains N space-separated integers representing the sequence. If N is 0, no further numbers are provided for that test case.

outputFormat

For each test case, output a single line to standard output (stdout) containing the maximum sum of any contiguous subarray for that test case.

## sample

2
9
-2 1 -3 4 -1 2 1 -5 4
4
-1 -2 -3 -4

6
-1

</p>