Maximum Subarray Sum Using Kadane's Algorithm

You are given an array of integers and your task is to find the maximum sum of any contiguous subarray. The maximum sum is defined as \(\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k\), where the array is \(a_1, a_2, \ldots, a_n\). This classic problem can be efficiently solved using Kadane's algorithm.

Note: In the case where all numbers are negative, the answer will be the maximum (least negative) number in the array.

inputFormat

The first line of input contains an integer \(T\) representing 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.

All input is read from standard input (stdin).

outputFormat

For each test case, output a single integer on a new line which is the maximum subarray sum computed from the given array. Output is written to standard output (stdout).

## sample

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

9
-1

</p>