Maximum Contiguous Subarray Sum

You are 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, \dots, a_n] \), you need to compute

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

This problem can be efficiently solved using Kadane's algorithm. Note that if the array contains all negative numbers, the answer is the largest (i.e. the least negative) element.

Example:

Input:  4
        -2 1 -3 4
Output: 4

inputFormat

The input is read from standard input. The first line contains an integer \( T \) representing the number of test cases. Each test case has the following format:

• 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 \( A \).

For example:

3
4
-2 1 -3 4
5
1 2 3 4 -10
8
8 -19 5 -4 20 -1 -1 -1

outputFormat

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

For the sample input above, the output should be:

4
10
21

## sample

1
4
-2 1 -3 4

4

</p>