Given an array of integers, return the maximum sum for a non-empty&nbsp;subarray (contiguous elements) with at most one element deletion.&nbsp;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&nbsp;sum of the remaining elements is maximum possible.

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

&nbsp;
Example 1:

Input: arr = [1,-2,0,3]
Output: 4
Explanation: Because we can choose [1, -2, 0, 3] and drop -2, thus the subarray [1, 0, 3] becomes the maximum value.

Example 2:

Input: arr = [1,-2,-2,3]
Output: 3
Explanation: We just choose [3] and it's the maximum sum.


Example 3:

Input: arr = [-1,-1,-1,-1]
Output: -1
Explanation:&nbsp;The final subarray needs to be non-empty. You can't choose [-1] and delete -1 from it, then get an empty subarray to make the sum equals to 0.


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 105
	-104 &lt;= arr[i] &lt;= 104


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        if n ==1:
            return arr[0]
        dpLeft = [-10**4-1 for _ in range(n)]
        dpLeft[0] = arr[0]
        i = 1 
        while i < n :
            dpLeft[i] = max(arr[i],dpLeft[i-1]+arr[i])
            i += 1
        dpRight = [-10**4-1 for _ in range(n)]
        dpRight[-1] = arr[-1]
        j = n-2 
        while j >= 0:
            dpRight[j] = max(arr[j],dpRight[j+1]+arr[j])
            j -= 1
        k = 0
        maxi = -10**4-1
        while k < n:
            # if we take it 
            curr_maxi_with = dpRight[k] + dpLeft[k] - arr[k]
            
            if k==0:
                curr_maxi_without = dpRight[k+1]
            elif k==n-1:
                curr_maxi_without = dpLeft[k-1]
            else:
                if dpLeft[k-1]>=0 and dpRight[k+1]>=0:
                    curr_maxi_without = dpRight[k+1] + dpLeft[k-1]
                else:
                    curr_maxi_without = max(dpLeft[k-1],dpRight[k+1])
            
            maxi= max(maxi,curr_maxi_without, curr_maxi_with)
            k += 1
        
        return maxi 
class Solution {
    public int maximumSum(int[] arr) {
        int n = arr.length;
        int[] prefixSum = new int[n+1];
        prefixSum[0] = 0;
        int ans = (int)-1e9;
        for(int i = 1; i <= n; i++){
            prefixSum[i] = prefixSum[i-1] + arr[i-1];
            ans = Math.max(ans, arr[i-1]);
        }
        if(ans < 0) return ans;  
        for(int i = 1; i <= n; i++){
            if(arr[i-1] < 0){
                int leftPrefixSum = 0;
                // find max in i to 0
                for(int j = i-1; j >= 0; j--){
                    leftPrefixSum = Math.max(leftPrefixSum, prefixSum[i-1] -prefixSum[j]);
                }
                
                int rightPrefixSum = 0;
                // find max in i to n
                for(int j = i+1; j <= n; j++){
                    rightPrefixSum = Math.max(rightPrefixSum, prefixSum[j] -prefixSum[i]);
                } 
                ans = Math.max(ans, leftPrefixSum + rightPrefixSum);
            }
        }
        return Math.max(ans, prefixSum[n]);
    }
}
class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int n = arr.size(), curr, maxi = INT_MIN;
        vector<int> fw(n + 1, 0), bw(n + 1, 0);
        fw[0] = arr[0];
        maxi = max(maxi, fw[0]);
        
		// ith element denotes the maximum subarray sum with ith element as the last element
        for(int i = 1; i < n; ++i) {
            curr = max(arr[i], fw[i - 1] + arr[i]);
            maxi = max(maxi, curr);
            fw[i] = curr;
        }
        
		// similar to fw array, but in the backward direction
        bw[n - 1] = curr = arr[n - 1];
        for(int i = n - 2; i >= 0; --i) {
            curr = max(arr[i], bw[i + 1] + arr[i]);
            maxi = max(maxi, curr);
            bw[i] = curr;
        }
        
        int res = INT_MIN;
        for(int i = 1; i < n - 1; ++i) {
            res = max(res, fw[i - 1] + bw[i + 1]);
        }
        return max(res, maxi);
    }
};
/**
 * @param {number[]} arr
 * @return {number}
 */
 

// var maximumSum = function(arr) {
//     const len = arr.length;
//     const dp = new Array(len).fill(() => [null, null]);
//     dp[0][0] = arr[0];
//     dp[0][1] = 0;
//     let result = arr[0];
//     for(let i = 1; i < len; i++) {
//         dp[i][1] = Math.max(dp[i-1][1] + arr[i], dp[i-1][0]);
//         dp[i][0] = Math.max(dp[i-1][0] + arr[i], arr[i]);
//         result = Math.max(result, Math.max(dp[i][0], dp[i][1]));  
//     }
    
//     return result;
// };

// optimization
var maximumSum = function(arr) {
    let noDelete = arr[0], oneDelete = 0, max = arr[0];
    for(let i = 1; i < arr.length; i++) {
        oneDelete = Math.max(oneDelete + arr[i], noDelete);
        noDelete = Math.max(noDelete + arr[i], arr[i]);
        max = Math.max(max, Math.max(noDelete, oneDelete));
    }
    return max;
};
Maximum Subarray Sum with One Deletion