Maximum Subarray Sum

You are given T test cases. In each test case, you are provided with an integer n followed by a list of n space-separated integers. Your task is to find the contiguous subarray which produces the maximum sum and output that sum.

The mathematical formulation is given by: $$max_sum = \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k$$.

A common algorithm to solve this problem is Kadane's algorithm. It efficiently computes the result in O(n) time per test case.

Process each test case independently and output the result on a new line.

inputFormat

The first line contains an integer T, the number of test cases. Each test case consists of two lines: the first line contains an integer n, representing the number of elements, and the second line contains n space-separated integers.

outputFormat

For each test case, output a line containing a single integer, the maximum subarray sum.## sample

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

7
-1
10