Maximum Subarray Sum

You are given a sequence of integers \(a_1, a_2, \ldots, a_n\). The task is to find the maximum sum of any contiguous subarray. In other words, find \(\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k\).

If all numbers are non-positive, the result should be the maximum (i.e., least negative) single element.

This classical problem can be solved efficiently using Kadane's algorithm with a time complexity of \(O(n)\).

inputFormat

The first line contains an integer \(T\) denoting the number of test cases. Each test case consists of two lines. The first line contains an integer \(N\), the size of 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 contiguous subarray sum.

## sample

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

6
-1

</p>