Greatest Sum of Subsequences

Given an integer sequence \(A = [a_1, a_2, \dots, a_n]\), determine the greatest sum obtainable by any non-empty subsequence of the sequence.

A subsequence is derived by deleting zero or more elements without changing the order of the remaining elements. Note that including any negative number in the subsequence might decrease the overall sum. Therefore, if there is at least one positive integer, the optimal strategy is to sum all positive numbers. However, if all numbers are non-positive, the answer is the maximum element in the sequence.

In mathematical terms, if there exists an \(a_i > 0\), then the answer is \(\sum_{a_i > 0} a_i\); otherwise, it is \(\max_{1 \leq i \leq n} a_i\).

inputFormat

The input begins with an integer \(T\) representing the number of test cases. Each test case is described in two lines:

• The first line contains an integer \(N\), the number of elements in the sequence.
• The second line contains \(N\) space-separated integers representing the sequence \(A\).

outputFormat

For each test case, output a single line containing the greatest sum of a non-empty subsequence.

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

8
-1