Maximum Sum of Positive Contiguous Subarray

You are given T test cases. In each test case, you are provided with an integer N followed by N integers representing the difficulty levels of puzzles. Your task is to find the maximum sum of any contiguous subarray that has a strictly positive total. If no such subarray exists, output 0.

The problem can be approached efficiently by using a variant of Kadane's algorithm. Formally, given an array \(A = [a_1, a_2, \ldots, a_N]\), find the maximum sum \(S\) such that there exists indices \(i\) and \(j\) with \(1 \leq i \leq j \leq N\) where

[ S = \sum_{k=i}^{j}a_k > 0 ]

If all contiguous subarrays produce non-positive sums, the answer should be \(0\). This problem requires careful initialization and update of the current sum to avoid negative accumulation.

inputFormat

The input is read from STDIN and has the following format:

• 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 elements in the array.
• The next line contains N space-separated integers representing the array.

outputFormat

For each test case, print a single line containing the maximum sum of any contiguous subarray with a strictly positive total. If no such subarray exists, print 0. The output is written to STDOUT.

## sample

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

5
6
0

</p>