Maximum Subarray Sum

Given an array of integers, your task is to find the maximum sum of a contiguous subarray. Formally, for an array \(a_1, a_2, \dots, a_n\), you need to compute

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

This is a classical problem which can be solved efficiently using Kadane's algorithm.

inputFormat

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

• The first line contains an integer \(n\) (the size of the array).
• The second line contains \(n\) space-separated integers, which are the elements of the array.

Constraints:

• 1 \(\leq T \leq 100\)
• 1 \(\leq n \leq 10^5\)
• The absolute value of each array element does not exceed \(10^9\).

outputFormat

For each test case, print a single line containing the maximum sum of any contiguous subarray.

## sample

1
5
1 2 -1 2 3

7

</p>