Maximum Subarray Sum

Given an integer array ( arr ), your task is to find the maximum possible sum of any non-empty contiguous subarray. This is a classic problem that can be solved using Kadane's algorithm.

For example, if ( arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4] ), the maximum subarray sum is ( 6 ), which corresponds to the subarray [4, -1, 2, 1].

inputFormat

The input begins with an integer ( T ) denoting 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 array. The second line contains ( n ) space-separated integers representing the array elements.

outputFormat

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

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

6
15