Maximum Contiguous Subarray Bonus

You are given T test cases. For each test case, you are provided with an array representing the productivity points of an employee over a series of days. Your task is to compute the maximum bonus that can be achieved by summing a contiguous subarray.

If all the productivity points are negative, the bonus is considered to be 0. Otherwise, it is the sum of the contiguous segment with the highest total.

The problem is a classic application of Kadane's algorithm. The bonus is equivalent to the maximum subarray sum (or 0 if all values are negative).

Note: All formulas are in \(\LaTeX\) format. For example, the maximum subarray sum algorithm can be summarized as:

[ max_current = \max(a_i, max_current + a_i)\quad\text{for each }a_i, \quad max_global = \max(max_global, max_current) ]

inputFormat

The input is read from stdin and is structured as follows:

• The first line contains an integer T, the number of test cases.
• For each test case:
• The first line contains an integer N, the number of days.
• The second line contains N space-separated integers representing the productivity points.

outputFormat

For each test case, output a single line to stdout containing the maximum bonus (i.e., maximum contiguous subarray sum or 0 if all numbers are negative).

## sample

1
4
-1 2 3 -4

5

</p>