Maximum Contiguous Subarray Sum

Given an integer array \(a\), your task is to find the contiguous subarray (containing at least one number) which has the largest sum, and return its sum. Formally, you need to compute:

\(\max_{1 \le i \le j \le n} \sum_{k=i}^{j} a_k\)

If all the numbers in the array are negative, return the maximum (i.e. the least negative) number.

inputFormat

The first line contains an integer \(T\) denoting the number of test cases. Each test case begins with an integer \(n\) specifying the size of the array, followed by a line with \(n\) space-separated integers representing the array elements.

Example:

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

outputFormat

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

Example Output:

4
-2

## sample

1
5
1 -2 3 -1 2

4

</p>