Maximum Subarray Sum

Given an array of integers, your task is to compute the maximum subarray sum for each test case. In other words, find a contiguous subsequence of the array such that the sum of its elements is maximized. This is a classic problem that can be solved efficiently using Kadane's algorithm. Note that if all numbers are negative, the maximum subarray sum is the largest (least negative) number.

The mathematical definition can be written in LaTeX as follows:

[ \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k ]

For each test case, read the input and output the computed maximum subarray sum.

inputFormat

The first line contains a single integer T, representing the number of test cases. Each test case consists of two lines:

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

All input should be read from stdin.

outputFormat

For each test case, output a single line containing the maximum sum of any contiguous subarray. The output should be written to stdout.

1
1
-5

-5