Code Implementation

class Solution:
    def maximumSum(self, arr):
        n = len(arr)
        max_end_here = arr[0]
        max_so_far = arr[0]
        max_end_here_del = float('-inf')
        for i in range(1, n):
            # max subarray sum ending at i with one deletion
            max_end_here_del = max(max_end_here, max_end_here_del + arr[i])
            # max subarray sum ending at i without deletion
            max_end_here = max(arr[i], max_end_here + arr[i])
            max_so_far = max(max_so_far, max_end_here, max_end_here_del)
        return max_so_far
    

class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int n = arr.size();
        int max_end_here = arr[0];
        int max_end_here_del = INT_MIN;
        int max_so_far = arr[0];
        for (int i = 1; i < n; ++i) {
            max_end_here_del = max(max_end_here, max_end_here_del + arr[i]);
            max_end_here = max(arr[i], max_end_here + arr[i]);
            max_so_far = max({max_so_far, max_end_here, max_end_here_del});
        }
        return max_so_far;
    }
};
    

class Solution {
    public int maximumSum(int[] arr) {
        int n = arr.length;
        int maxEndHere = arr[0];
        int maxEndHereDel = Integer.MIN_VALUE;
        int maxSoFar = arr[0];
        for (int i = 1; i < n; i++) {
            maxEndHereDel = Math.max(maxEndHere, maxEndHereDel + arr[i]);
            maxEndHere = Math.max(arr[i], maxEndHere + arr[i]);
            maxSoFar = Math.max(maxSoFar, Math.max(maxEndHere, maxEndHereDel));
        }
        return maxSoFar;
    }
}
    

var maximumSum = function(arr) {
    let n = arr.length;
    let maxEndHere = arr[0];
    let maxEndHereDel = -Infinity;
    let maxSoFar = arr[0];
    for (let i = 1; i < n; i++) {
        maxEndHereDel = Math.max(maxEndHere, maxEndHereDel + arr[i]);
        maxEndHere = Math.max(arr[i], maxEndHere + arr[i]);
        maxSoFar = Math.max(maxSoFar, maxEndHere, maxEndHereDel);
    }
    return maxSoFar;
};
    

Problem Description

Given an integer array arr, you are allowed to perform at most one operation: remove a single element from arr. After this operation (or without removing any element), find the maximum possible sum of a non-empty subarray. A subarray is a contiguous sequence of elements in the array. The removed element does not have to be part of the chosen subarray.

• Input: an integer array arr
• Output: an integer, the maximum sum of a non-empty subarray after at most one deletion
• You may choose not to delete any element
• The subarray must be non-empty and contiguous
• Each element can be used at most once in the subarray
• There is always at least one valid answer

Thought Process

The classic "maximum subarray sum" problem is solved using Kadane's algorithm, which efficiently finds the largest sum of a contiguous subarray in linear time. However, this problem introduces a twist: you can remove at most one element to try to increase the sum.

At first glance, a brute-force approach might seem reasonable: for each index, remove it and compute the maximum subarray sum of the resulting array. But this would be too slow for large arrays.

The key insight is that we can track two states as we scan through arr:

• The maximum subarray sum ending at the current index with no deletions
• The maximum subarray sum ending at the current index with exactly one deletion

Solution Approach

Let's break down the dynamic programming strategy step by step:

1. Define Two States:
   • max_end_here: The maximum subarray sum ending at the current index with no deletion.
   • max_end_here_del: The maximum subarray sum ending at the current index with one deletion.
2. Initialization:
   Both states start with arr[0], except max_end_here_del starts with negative infinity (since we can't delete before the first element).
3. Transition:
   • max_end_here = max(arr[i], max_end_here + arr[i])
   • max_end_here_del = max( max_end_here,   // delete current element max_end_here_del + arr[i] // continue after previous deletion )
4. Result:
   • At each index, update a variable max_so_far to track the maximum among max_end_here and max_end_here_del.
   • Return max_so_far at the end.

This approach ensures that for every position, we consider both the case of not deleting any element and the case where we have already deleted one element somewhere before or at the current position.

Example Walkthrough

Let's walk through the input arr = [1, -2, 0, 3] step by step.

• Initialize: max_end_here = 1, max_end_here_del = -inf, max_so_far = 1
• i = 1 (arr[1] = -2):
  
  • max_end_here_del = max(1, -inf + -2) = 1
  • max_end_here = max(-2, 1 + -2) = -1
  • max_so_far = max(1, -1, 1) = 1
• i = 2 (arr[2] = 0):
  
  • max_end_here_del = max(-1, 1 + 0) = 1
  • max_end_here = max(0, -1 + 0) = 0
  • max_so_far = max(1, 0, 1) = 1
• i = 3 (arr[3] = 3):
  
  • max_end_here_del = max(0, 1 + 3) = 4
  • max_end_here = max(3, 0 + 3) = 3
  • max_so_far = max(1, 3, 4) = 4

So the answer is 4, which comes from the subarray [0, 3] after deleting -2.

Time and Space Complexity

Brute-force Approach:
For each index, remove it and compute the maximum subarray sum of the remaining array (using Kadane's, O(n)), for a total of O(n^2).

Optimized Approach (Dynamic Programming):
We process the array in one pass, maintaining two states at each step. Each operation is O(1), so the total time complexity is O(n).
Space complexity is O(1) as we only store a constant number of variables.

Summary

The "Maximum Subarray Sum After One Operation" problem extends the classic maximum subarray problem by allowing at most one deletion. By tracking two states—one for the normal subarray sum and one for the sum with a deletion—we efficiently find the best possible result in linear time. The elegance of this solution lies in its simplicity and its ability to handle both cases (with or without deletion) using a dynamic programming approach with constant space.