Maximum Subarray Sum with One Removal

Given an array of integers, your task is to compute the maximum sum of any contiguous subarray when you are allowed to remove at most one element from that subarray. In other words, you can choose to skip one element in order to maximize the sum.

Formally, if the array is denoted by \(a_1, a_2, \ldots, a_n\), you want to find the maximum possible value of the sum of a contiguous segment after removing at most one element. Note that you are allowed not to remove any element at all. The problem requires you to use efficient dynamic programming techniques.

For example, consider the array [1, -2, 0, 3, 2]. The maximum sum obtainable is 6, which can be achieved by removing -2 and taking the subarray [1, 0, 3, 2].

inputFormat

The first line of input contains an integer \( n \), the number of elements in the array. The second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

Output a single integer, which is the maximum contiguous subarray sum that can be obtained when you are allowed to remove at most one element.

5
1 -2 0 3 2

6