Maximum Subarray Sum

You are given an array of integers. Your task is to find the maximum sum of any contiguous subarray using Kadane's algorithm.

If all numbers are negative, the answer is the maximum (least negative) number.

Note: A subarray is a contiguous part of the array.

The formula for updating the maximum is given by the recurrence:

\( maxCurrent = \max( a_i, maxCurrent + a_i ) \)

and the final answer is \( maxGlobal = \max( maxGlobal, maxCurrent ) \) over all elements.

inputFormat

The first line contains an integer \(T\) which represents the number of test cases. Each test case consists of two lines: the first line contains an integer \(n\) representing the size of the array, and the second line contains \(n\) space-separated integers.

Example:

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

outputFormat

For each test case, output a single line containing the maximum subarray sum.

Example Output:

4
-1
10

## sample

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

4
-1
10

</p>