Maximum Subarray Sum Using Kadane's Algorithm

This problem requires you to compute the maximum subarray sum of an array using Kadane's algorithm. Given a series of test cases, each consisting of an array of integers, your task is to output the sum of the subarray with the largest sum for each test case.

The algorithm should handle both positive and negative numbers and must work efficiently even on larger inputs.

Note: The input starts with an integer T indicating the number of test cases. For each test case, the first number is an integer N denoting the number of elements, followed by N space-separated integers.

inputFormat

The first line of input contains an integer T, the number of test cases. For each test case, there are two lines:

• 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 elements.

All input is provided via standard input (stdin).

outputFormat

For each test case, output a single line containing the maximum subarray sum. All output must be written to standard output (stdout).

## sample

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

8
-1

</p>