Maximum Subarray Sum

Given an array of integers, find the contiguous subarray (containing at least one number) which has the largest sum.

This is a classic problem often solved using Kadane's algorithm. The algorithm works by iteratively updating two values:

• max_current: the maximum sum of a subarray ending at the current position, computed as $$max\_current = \max(a_i, max\_current + a_i)$$
• max_global: the overall maximum subarray sum found so far, computed as $$max\_global = \max(max\_global, max\_current)$$

If all the elements are negative, the maximum subarray is the largest (least negative) element.

inputFormat

The first line of input contains an integer T, representing the number of test cases. Each test case consists of two lines:

• The first line contains an integer n, the number of elements in the array.
• The second line contains n space-separated integers representing the array elements.

outputFormat

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

## sample

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

6
-1

</p>