Maximum Subarray Sum with One Deletion

Problem:

Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.

Note that the subarray needs to be non-empty after deleting one element.

Example 1, [1, -2, 0, 3] ~ The maximum sum should be 4, we choose all elements and remove -2

Example 2, [1, -2, -2, 3] ~ The maximum sum should be 3, we choose [-2,3] and we remove -2

Example 3, [-2, -3, 4, -1, -2, 1, 5] ~ The maximum sum should be 9, we choose [4, -1, -2, 1, 5] and remove -2

Approach:

So, our main goal is to Choose a subarray which size is at least 2, and after removing 1 element we have to make the sum of choosing subarray after that we have to maximize this sum.

We can solve this problem by building a forward and a backward array, and its kind of DP.

What we say earlier, we will make two array of maximum subarray sum from forward(left to right) and another from backward(right to left).

Formaly what we can get from this array ?

suppose forward array, in every element of ith position will say this is the maximum subarray sum untill this position.

Build forward array bay maximizing previous value of forward element + current value of original element with current value of original element.

Similarly backward array will be build this way. 

Firstly we make forward and backward array, at the same time we maximize an Ans value by checking current value of forward and backward array.

And finally we traverse whole array and  tried to remove every element and take sum of forward or backward maximum subarray value.