Maximum Subarray Sum

This problem requires you to find the maximum sum of any contiguous subarray within a given array of integers. The challenge is to implement an efficient algorithm, typically using Kadane's algorithm, which operates in \(O(n)\) time. You will be provided with multiple test cases. For each test case, you need to read the array data from standard input and output the maximum subarray sum to standard output.

Input Format: The first line contains an integer \(T\) denoting the number of test cases. Each test case starts with an integer \(N\) that represents the length of the array, followed by a line containing \(N\) space-separated integers.

Output Format: For each test case, print the maximum contiguous subarray sum on a new line.

inputFormat

The first line contains an integer \(T\) specifying the number of test cases. For each test case:

• The first line contains an integer \(N\), the number of elements in the array.
• The second line contains \(N\) space-separated integers representing the array.

outputFormat

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

## sample

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

10
7
3

</p>