Maximum Subarray Sum

Given an array of integers, your task is to determine the maximum sum of any contiguous subarray. This is a classic problem that can be efficiently solved using Kadane's Algorithm. The recurrence relation in Kadane's algorithm is given by: $$max\_current = \max(a_i, max\_current + a_i)$$, where \(a_i\) denotes the current element.

You are required to process multiple test cases. For each test case, compute the maximum subarray sum and output it on a new line.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer T representing the number of test cases.
• For each test case, the first line contains an integer N denoting the number of elements in the array.
• The next line contains N space-separated integers representing the elements of the array.

outputFormat

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

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

10
6
-1
23
-1