Maximum Score from Targets

You are given a series of archery targets, each with a specified point value. In each test case, your task is to determine the maximum score that Archery King can achieve by hitting a contiguous sequence of targets. This problem can be modeled as finding the maximum subarray sum.

Formally, given an array \(a_1, a_2, \dots, a_n\), you need to compute the value:

[ \max_{1 \leq i \leq j \leq n} \left(\sum_{k=i}^{j} a_k\right) ]

Note that the sequence of targets must be contiguous. If all the target scores are negative, then the maximum score is the largest (least negative) value.

Example:

Input:
2
4
-1 3 -2 5
5
1 -2 0 4 -3
Output:
6
4

</p>

inputFormat

The input is read from stdin and follows this format:

• 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 number of targets.
  • The second line contains \(n\) space-separated integers representing the point values of the targets.

For example:

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

outputFormat

For each test case, print a single line to stdout containing one integer --- the maximum achievable score from a contiguous sequence of targets.

For example, the output for the sample input is:

6
4

## sample

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

6
4

</p>