Maximum Subarray Sum

Given an array of integers, your task is to compute the maximum sum of any contiguous subarray. This is a classic problem that can be efficiently solved using Kadane's algorithm. The algorithm works by maintaining a running maximum that is updated as you traverse the array. Formally, if the array is \(a_1, a_2, \dots, a_n\), the recurrence for the running maximum is defined as:

\(dp[i] = \max(a_i, dp[i-1] + a_i)\) with \(dp[1] = a_1\).

The final answer is \(\max_{1 \le i \le n} dp[i]\).

Efficiently implement this algorithm to handle multiple test cases.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each of the following \(T\) lines represents a test case and begins with an integer \(N\) denoting the number of elements in the array, followed by \(N\) space-separated integers.

outputFormat

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

## sample

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

7
-1
5
-5
15
-1
10

</p>