Maximum Subarray Sum with One Deletion

medium dynamic programming kadane array

Problem

Given an array of integers arr, return the maximum sum of a non-empty subarray (contiguous elements) with at most one element deletion. After deleting one element the subarray must still be non-empty. Note that the subarray needs to be non-empty after deleting one element.

Inputarr = [1, -2, 0, 3]

Output4

Delete the -2, leaving the subarray [0, 3] joined to the leading 1 → 1 + 0 + 3 = 4.

arr (comma-separated)

def maximum_sum(arr):
    no_del = arr[0]
    one_del = arr[0]
    best = arr[0]
    for x in arr[1:]:
        one_del = max(one_del + x, no_del)
        no_del = max(no_del + x, x)
        best = max(best, no_del, one_del)
    return best

function maximumSum(arr) {
  let noDel = arr[0];
  let oneDel = arr[0];
  let best = arr[0];
  for (let i = 1; i < arr.length; i++) {
    const x = arr[i];
    oneDel = Math.max(oneDel + x, noDel);
    noDel = Math.max(noDel + x, x);
    best = Math.max(best, noDel, oneDel);
  }
  return best;
}

class Solution {
    public int maximumSum(int[] arr) {
        int noDel = arr[0];
        int oneDel = arr[0];
        int best = arr[0];
        for (int i = 1; i < arr.length; i++) {
            int x = arr[i];
            oneDel = Math.max(oneDel + x, noDel);
            noDel = Math.max(noDel + x, x);
            best = Math.max(best, Math.max(noDel, oneDel));
        }
        return best;
    }
}

int maximumSum(vector<int>& arr) {
    int noDel = arr[0];
    int oneDel = arr[0];
    int best = arr[0];
    for (int i = 1; i < (int)arr.size(); i++) {
        int x = arr[i];
        oneDel = max(oneDel + x, noDel);
        noDel = max(noDel + x, x);
        best = max(best, max(noDel, oneDel));
    }
    return best;
}

Explanation

This is Kadane's algorithm with a twist: alongside the normal "best sum ending here", we keep a second running value for "best sum ending here if we've already used our one allowed deletion".

We carry two states as we sweep left to right. no_del is the best subarray sum ending at the current element with no deletion. one_del is the best ending here where exactly one element somewhere inside has been removed.

For each new value x: one_del = max(one_del + x, no_del) — either extend an already-deleted run, or delete x itself by jumping from the no-deletion run that ended just before it. Then no_del = max(no_del + x, x), the plain Kadane update. We track the running best across both.

Example: arr = [1, -2, 0, 3]. By the time we reach 3, deleting the -2 lets the run 1 + 0 + 3 = 4 count as one subarray, and that 4 is the answer.

Only a constant amount of state is updated per element, so this is a single O(n) pass using O(1) extra space.

Time: O(n) Space: O(1)