Maximum Sum Subarray with One Removal

Given an array of integers, your task is to find the maximum sum of any contiguous subarray that can be achieved by removing at most one element. In other words, you are allowed to delete at most one element from the array to maximize the sum of a contiguous segment.

You may consider the case when no removal is needed if the maximum sum is achieved using all elements. Note that the answer might be negative if all numbers are negative.

The problem can be formulated using the following recurrences:

\( L[i] = \max(a_i, L[i-1] + a_i) \) for the maximum subarray sum ending at index \(i\), and similarly for the reverse direction. Then, for each possible removal at index \(j\) (where \(1 \leq j \leq n-2\)), the solution can be computed as:

\( \text{answer} = \max( L[j-1] + R[j+1] ) \)

inputFormat

The input is given via standard input. The first line contains a single integer \(n\) (the size of the array). The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single integer, the maximum sum of a contiguous subarray after removing at most one element.

6
1 -2 0 3 -1 2

5