Maximum Contiguous Subarray Sum

You are given an array of integers. Your task is to find the maximum sum of any contiguous subarray. More formally, given an array \(a_1, a_2, \dots, a_n\), you need to compute:

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

This problem is a classic which can be efficiently solved using Kadane's algorithm. Beware that the array may contain all negative numbers, in which case the answer is the maximum (i.e. the least negative) element.

inputFormat

The first line of input contains an integer \(T\) denoting the number of test cases. Each test case begins with an integer \(N\) on a new line, representing the number of elements in the array. The next line contains \(N\) space-separated integers denoting the elements of the array.

Example:

3
8
1 -2 3 4 -1 2 1 -5
5
-2 -3 -4 -1 -2
6
-1 2 3 -2 3 4

outputFormat

For each test case, output a single line containing the maximum sum that can be obtained from any contiguous subarray.

Example Output:

9
-1
10

## sample

3
8
1 -2 3 4 -1 2 1 -5
5
-2 -3 -4 -1 -2
6
-1 2 3 -2 3 4

9
-1
10

</p>