Maximum Contiguous Subarray Sum

Given an array of integers, find the maximum sum of any non-empty contiguous subarray. This is a classic problem that can be solved using Kadane's algorithm. Formally, for an array \(a_1, a_2, \dots, a_n\), you are to find \(\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k\). The input consists of multiple test cases.

inputFormat

The first line contains an integer (T), the number of test cases. Each test case starts with an integer (N), representing the number of elements in the array, followed by a line with (N) space-separated integers.

outputFormat

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

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

3
-1