Maximum Contiguous Subarray Sum

Given an array of integers, your task is to find the maximum possible sum of any contiguous subarray. In other words, for 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 \)

If the array is empty, return 0. This is a classic problem often solved using Kadane's algorithm.

inputFormat

The input is read from standard input (stdin) and follows the format below:

• The first line contains an integer \(T\) representing the number of test cases.
• For each test case, the first line contains an integer \(n\) denoting the number of elements in the array.
• The second line contains \(n\) space-separated integers.

outputFormat

For each test case, output the maximum contiguous subarray sum on a new line to standard output (stdout).

## sample

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

2
-1 2

7
7
-1
0
2

</p>