Maximum Sum Contiguous Subarray

Given an integer array, your task is to find the maximum sum of a contiguous subarray. This is a classic problem that can be solved using Kadane's Algorithm. Note that if all numbers are negative, the contiguous subarray with the maximum sum is the one with the least negative (i.e., the maximum) element.

Example:

Input:  [ -2, -3, 4, -1, -2, 1, 5, -3 ]
Output: 7
Explanation: The contiguous subarray with the maximum sum is [4, -1, -2, 1, 5] which sums up to 7.

</p>

inputFormat

The first line of input contains a single integer T denoting the number of test cases. For each test case, the first line contains an integer n representing the number of elements in the array. The second line contains n space-separated integers representing the array.

outputFormat

For each test case, output a single line containing the maximum sum of a contiguous subarray.

## sample

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

7
-1

</p>