Maximum Subarray Sum

You are given an array of integers. Your task is to find the maximum subarray sum, which is the largest sum of a contiguous subarray.

For an array \(A = [a_1, a_2, \dots, a_n]\), the maximum subarray sum is defined as

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

This problem can be solved efficiently using Kadane's algorithm. It correctly handles arrays with both positive and negative numbers.

Example:

• For the array [1, -2, 3, 4, -5], the maximum subarray sum is 7, which comes from the subarray [3, 4].
• For the array [-1, -2, -3, -4, -5], the maximum subarray sum is -1 (taking the single element -1).

inputFormat

The first line of input contains an integer T, denoting 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 representing the array elements.

outputFormat

For each test case, output a single integer representing the maximum subarray sum. Print each output on a new line.## sample

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

7
8

</p>