Maximum Subarray Sum

Given an array of integers, your task is to find the maximum possible sum of any contiguous subarray. This is a classic problem that can be efficiently solved using Kadane's algorithm.

Note: The maximum subarray is the contiguous section with the largest sum. The formula for updating the current maximum is given by:

$$max_{current} = \max(a_i, max_{current} + a_i)$$

and the global maximum is updated as:

$$max_{global} = \max(max_{global}, max_{current}).$$</p> ## inputFormat

The first line of input contains an integer T representing the number of test cases. Each test case is defined as follows:

• The first line contains an integer n, the number of elements in the array.
• The second line contains n space-separated integers representing the elements of the array.

## outputFormat

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

## sample

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

10
23
9

$$