Maximum Subarray Sum

Given an array of integers, the task is to find the maximum sum obtainable from any contiguous subarray.

Formally, given an array \(a_1, a_2, \dots, a_n\), you need to compute:

\(\max_{1 \le i \le j \le n} \left(\sum_{k=i}^{j} a_k\right)\)

You must process multiple test cases. For each test case, compute the maximum subarray sum using an efficient method (Kadane's algorithm is recommended).

inputFormat

The first line 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), followed by a line with (n) space-separated integers.

outputFormat

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

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

4
6