Maximum Subarray Sum

Given a sequence of integers that may include both positive and negative values, determine the maximum sum of any contiguous subarray for each test case.

In other words, for each test case, find a non-empty contiguous segment of the array such that the sum of its elements is maximized. This problem can be efficiently solved using Kadane's algorithm.

It is guaranteed that each array contains at least one element when the number of elements is greater than zero.

inputFormat

The input is read from standard input (stdin). The first line contains an integer T, the number of test cases. For each test case, the first line contains an integer N representing the number of elements in the array, and the second line contains N space-separated integers representing the array elements.

outputFormat

For each test case, print a single line to standard output (stdout) containing the maximum sum of any contiguous subarray.## sample

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

6
7
-1