Maximum Subarray Sum

In this problem, you are given an array of integers and you need to find the maximum possible sum of a contiguous subarray. This is a classic problem that can be solved efficiently using Kadane's algorithm. The key idea is to use the recurrence [ max_ending_here = \max(a[i],, a[i] + max_ending_here)] for each element in the array and maintain the overall maximum.

Problem Statement: Given an integer T representing the number of test cases, and for each test case an integer N followed by N integers (the array), find the maximum sum of any contiguous subarray for each test case.

inputFormat

The first line of input contains a single integer T, the number of test cases.

For each test case, the first line contains an integer N representing 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 the maximum sum of a contiguous subarray in a new line.

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

7
-1
3