Maximum Subarray Sum With One Deletion - Leetcode Solution

Problem Statement: 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.

Example:

Input: [1,-2,0,3] Output: 4 Explanation: We can delete -2 to get [1,0,3]. Then, the max subarray sum is 1+0+3 = 4.

Approach:

1. First we iterate forward once to calculate the maximum subarray sum ending at each position i.

2. Next, we iterate backward once to calculate the maximum subarray sum starting from each position i.

3. Now, we can check for each position i what the maximum sum is: either the sum of the subarray ending at i or the sum of the subarray starting at i-1. If we delete any element at position i, our maximum sum can be updated with the sum of both these subarrays.

4. We return the overall maximum sum from the above step.

Implementation:

The above algorithm can be implemented as follows:

class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int n = arr.size();
        vector<int> max_end(n); // maximum subarray sum ending at each position
        vector<int> max_start(n); // maximum subarray sum starting from each position
        
        // forward pass
        int running_sum = 0;
        for(int i = 0; i < n; i++){
            running_sum = max(arr[i], running_sum + arr[i]);
            max_end[i] = running_sum;
        }
        
        // backward pass
        running_sum = 0;
        for(int i = n-1; i >= 0; i--){
            running_sum = max(arr[i], running_sum + arr[i]);
            max_start[i] = running_sum;
        }
        
        int ans = INT_MIN;
        // check for each position i what the maximum sum is
        for(int i = 0; i < n; i++){
            ans = max(ans, max_end[i]);
            if(i > 0){
                ans = max(ans, max_start[i-1]);
                ans = max(ans, max_end[i-1] + max_start[i]);
            }
        }
        
        return ans;
    }
};

Time complexity: O(n), where n is the length of the input array.

Space complexity: O(n), as we are creating two vectors of size n.

1