Maximum Subarray Sum

You are given an array of integers. Your task is to find the contiguous subarray (containing at least one number) which has the largest sum, and output this sum.

This problem can be solved using Kadane's Algorithm. The idea behind the algorithm is to use the recurrence relation \[ current = \max(a_i, current + a_i), \] and update the result as \[ best = \max(best, current). \]

Please note that the input consists of multiple test cases. For each test case, the first line contains an integer n denoting the length of the array, followed by a line containing n space-separated integers.

inputFormat

The input is given via stdin and is structured as follows:

• The first line contains a positive integer T representing the number of test cases.
• For each test case, the first line contains an integer n (the length of the array).
• The second line contains n space-separated integers representing the array.

outputFormat

For each test case, output the maximum subarray sum on a separate line to stdout.

1
9
-2 1 -3 4 -1 2 1 -5 4

6