Implement the solution to the Maximum Sum Subarray Removing at Most One Element problem using dynamic programming.?

The Maximum Sum Subarray Removing at Most One Element problem requires finding the maximum contiguous subarray sum that can be obtained by removing at most one element from the array. This problem can be solved using dynamic programming with a time complexity of O(n).

The idea is to maintain two arrays, left and right. The left array stores the maximum sum subarray ending at each index of the input array moving from the left to right, whereas the right array stores the maximum sum subarray starting at each index of the input array moving from right to left. Then, we can iterate through the input array and for each index i, we can find the maximum sum subarray that can be obtained by removing the ith element by adding the maximum left subarray sum ending at index i-1 to maximum right subarray sum starting at index i+1.

Here is the Java implementation of the dynamic programming solution to the Maximum Sum Subarray Removing at Most One Element problem:

public int maxSubArrayRemovingOne(int[] nums) {
    int n = nums.length;
    int[] left = new int[n];
    int[] right = new int[n];
    
    // finding maximum subarray sum ending at each index moving left to right
    int maxEndingHere = nums[0];
    left[0] = nums[0];
    for(int i = 1; i < n; i++) {
        maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]);
        left[i] = Math.max(left[i-1], maxEndingHere);
    }
    
    //finding maximum subarray sum starting at each index moving right to left
    maxEndingHere = nums[n-1];
    right[n-1] = nums[n-1];
    for(int i = n-2; i >= 0; i--) {
        maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]);
        right[i] = Math.max(right[i+1], maxEndingHere);
    }
    
    //finding maximum contiguous subarray sum that can be obtained by removing at most one element
    int maxSum = left[0];
    for(int i = 1; i < n-1; i++) {
        maxSum = Math.max(maxSum, left[i-1] + right[i+1]);
    }
    return maxSum;
}

Let’s consider an example to understand the implementation better. Let’s say we have an input array ‘nums = [4, -3, 5, -2, -1, 2, 6, -2]‘. The expected output is ‘14‘, which is the maximum contiguous subarray sum that can be obtained by removing at most one element.

Using the above implementation, we get ‘left = [4, 4, 9, 7, 6, 8, 14, 12]‘ and ‘right = [14, 14, 14, 14, 14, 8, 6, -2]‘. Then, we iterate through the input array and calculate the maximum sum subarray that can be obtained by removing the ith element by adding the maximum left sum ending at ‘i-1‘ to the maximum right sum starting at ‘i+1‘. We get ‘maxSum = max(4+14, 4+14, 9+14, 7+14, 6+14, 8+6, 14-2) = 14‘. Hence, we get the expected output of ‘14‘.