Maximum Subarray Sum

Given an integer sequence, your task is to find the maximum sum of any contiguous subsequence. This is a classic problem known as the Maximum Subarray Problem and can be solved efficiently using Kadane's algorithm.

For each test case, you are provided with a sequence of integers. Your goal is to find the contiguous subarray (containing at least one element) that has the largest sum and output that sum.

inputFormat

The input begins with an integer T (the number of test cases). Each test case consists of two lines:

• The first line contains an integer N representing the number of elements in the sequence.
• The second line contains N space-separated integers denoting the sequence.

outputFormat

For each test case, output a single integer on a new line, which is the maximum contiguous subarray sum for the given sequence.

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

10
4