Maximum Subarray Sum

Given an array of integers, your task is to find the maximum sum of any contiguous subarray. Formally, for an array \(A = [a_1, a_2, \ldots, a_n]\), you need to compute the maximum possible sum for any subarray \(A[i \ldots j]\) where \(1 \leq i \leq j \leq n\). This problem can be efficiently solved using Kadane's algorithm.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. For each test case, the first line contains an integer \(N\) (the number of elements in the array), followed by a second line that contains \(N\) space-separated integers.

outputFormat

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

1
5
1 2 3 4 5

15