Maximum Sum Subsequence with Alternating Signs

In this problem, you are given an array of integers. Your task is to compute the maximum sum of a subsequence, constructed by selecting numbers from the array sequentially, such that no two consecutive numbers in the chosen subsequence have the same sign. In other words, starting from the first element, add subsequent elements only if it has an opposite sign compared to its immediate predecessor in the array.

More formally, let (a_1, a_2, \dots, a_n) be the given array. Define (S = a_1 + \sum_{i=2}^{n} [a_i \text{ is added if } a_i \times a_{i-1} < 0]). If the array is empty, the answer is 0.

Examples:

• For the array [1, -2, 3, -4, 5]: The subsequence is 1, -2, 3, -4, 5 and its sum is 3.
• For the array [1, -2, -3, 4, -5, 6]: The subsequence is 1, -2, 4, -5, 6 and its sum is 4.
• For the array [1, 2, 3]: Only the first element is taken, so the output is 1.
• For the array [-1, -2, -3]: Only the first element is taken, so the output is -1.

It is guaranteed that the input format satisfies the constraints and the numbers are given in the order as they appear in the array.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains a single 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 second line contains (n) space-separated integers representing the array elements.

For example:

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

outputFormat

For each test case, output a single line containing the maximum sum computed following the rule described above. The results for different test cases should be printed on separate lines via the standard output (stdout).## sample

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

3
4
5
1
-1