Maximum Subarray Sum

You are given an integer \(T\) representing the number of test cases. For each test case, an integer \(n\) is given followed by \(n\) space-separated integers that constitute an array. Your task is to compute the maximum possible sum of any contiguous non-empty subarray for each test case.

This problem can be formally stated as follows: Given an array \(a_1, a_2, \dots, a_n\), find the maximum value of \(\sum_{i=j}^{k} a_i\) for \(1 \leq j \leq k \leq n\). One efficient way to solve this problem is by using Kadane's algorithm, where the recurrence is given by:

[ \text{current} = \max(a_i, \text{current} + a_i) \quad \text{and} \quad \text{best} = \max(\text{best}, \text{current}) ]

Note that even if all numbers are negative, you must choose at least one element.

inputFormat

The input is given from standard input (stdin). The first line contains a single integer (T), denoting the number of test cases. For each test case:

• The first line contains an integer (n) — the length of the array.
• The second line contains (n) space-separated integers representing the array elements.

outputFormat

For each test case, output a single line to standard output (stdout) that contains the maximum subarray sum.## sample

1
5
1 -2 3 4 -1

7