Maximum Subarray Sum

Given an array of integers, find the contiguous subarray (containing at least one number) which has the largest sum and output that sum. The problem can be formally defined as finding the maximum over all subarrays:

\(\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} A_k\)

This problem can be efficiently solved using Kadane's algorithm in \(O(n)\) time.

inputFormat

The input begins with an integer \(T\) denoting 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 elements.

outputFormat

For each test case, print a single line containing the maximum subarray sum.

## sample

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

9
-1

</p>