1186. Maximum Subarray Sum with One Deletion

Link

Solution

The max value will belong to the two cases

1. No deletion, same as the 53 maximum subarray

2. One Deletion, assume arr[i] is deleted, then the max sum will be : dpStart[i+1] + dpEnd[i-1]

 public int maximumSum(int[] arr) {
        int n = arr.length;
        int[] dpEnd = new int[n];
        int[] dpStart = new int[n];
        dpEnd[0] = arr[0];
        int max = dpEnd[0];
        
        
        for(int i = 1; i < n; i++){
            dpEnd[i] = dpEnd[i-1] < 0? arr[i] : dpEnd[i-1] + arr[i];
            max = Math.max(max, dpEnd[i]);
        }
        dpStart[n-1] = arr[n-1];
        for(int i = n-2; i >= 0; i--){
            dpStart[i] = dpStart[i+1] < 0 ? arr[i] : arr[i] + dpStart[i+1];
        }
        
        for(int i = 1; i < n-1; i++){
            if(arr[i] < 0){
                max = Math.max(max, dpEnd[i-1] + dpStart[i+1]);
            }
        }
        return max;
        
    }