Max and Min Subarray Sums

You are given $T$ test cases. For each test case, you are provided with an integer $n$ followed by $n$ integers representing an array. Your task is to find the maximum contiguous subarray sum and the minimum contiguous subarray sum for each test case.

The maximum subarray sum is the largest possible sum of a contiguous subarray, and the minimum subarray sum is the smallest possible sum of a contiguous subarray. Use the well-known Kadane's algorithm to solve these problems efficiently.

Formally, given an array $a_1, a_2, \dots, a_n$, find: [ \text{maxSum} = \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k, \quad \text{minSum} = \min_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k. ]

inputFormat

The first line of input contains an integer $T$, the number of test cases. Each test case starts with an integer $n$ on a new line, 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 two space-separated integers: the maximum subarray sum and the minimum subarray sum.## sample

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

9 -2
-1 -10