Maximum Subarray Sum with One Exclusion

You are given an array of integers. Your task is to find the maximum possible sum of a contiguous subarray when you are allowed to remove at most one element from that subarray. Removing an element may help improve the overall sum if that element is negative.

Formally, let \( a_1, a_2, \dots, a_n \) be the array. You need to compute:

\[ \max_{1 \leq i \leq j \leq n} \left( \sum_{k=i}^{j} a_k - \min\{0, a_m\} \right) \]

where the exclusion of \( a_m \) is optional (applied at most once) and must preserve contiguity of the remaining elements.

inputFormat

The input begins with an integer \(T\) (the number of test cases). Each test case starts with an integer \(n\) representing the number of elements in the array. This is followed by a line containing \(n\) integers separated by spaces, representing the array elements.

outputFormat

For each test case, output a single integer on a new line: the maximum sum of a contiguous subarray obtainable after excluding at most one element.

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

4
-1