Maximum Subarray Sum with One Deletion

1. Define the problem

Maximum Subarray Sum with One Deletion

Given an integer array arr, return the maximum sum of a non-empty subarray, where you are allowed to delete at most one element from it. The subarray must still be non-empty after the deletion. This is ordinary Kadane's with a second decision layered on top: at every index, track two running sums — one that has not used its deletion yet, and one that already has — and let a run switch from the first to the second by dropping exactly one element.

Constraints

1 ≤ arr.length ≤ 10⁵
-10⁴ ≤ arr_i ≤ 10⁴

Example

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

Output4

Explanation Deleting -2 leaves [1, 0, 3], which sums to 4.

2. Know the words first

In plain terms

Two running sums: noDeletion tracks the best run ending here with ordinary Kadane's rules. oneDeletion tracks the best run ending here that has already used its one allowed deletion — either by deleting the current element (carrying forward noDeletion from the step before) or by extending a run that deleted an earlier element.

3. Visualize the solution

Carry two running sums: one deletion-free, one already spent

1-2

StatusnoDeletion: 1 · oneDeletion: — · best: 1

Seed noDeletion with the first element, 1. No deletion has been used yet.

What happens in this step

arr[0] = 1

noDeletion = 1
oneDeletion = 0  (not a real run yet — no deletion has happened)
best = 1

Seed noDeletion with the first element; oneDeletion starts at its initial 0 but represents no run yet.

Step 1 of 4

Steps to visualize

The row is the input array, [1, -2, 0, 3]. The frame marks the best run found so far, counting a deleted element as still inside the run.
Seed noDeletion with the first element. There is no oneDeletion run yet.
At each later index, compute the new oneDeletion first, using the noDeletion value from before this step: either delete the current element (keep the old noDeletion) or extend a run that already deleted something earlier.
Then compute the new noDeletion the ordinary Kadane way: extend or restart with the current element.
Track the best value seen across both running sums at every step.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Carry two running sums: one deletion-free, one already spent

1-2

StatusnoDeletion: 1 · oneDeletion: — · best: 1

Seed noDeletion with the first element, 1. No deletion has been used yet.

What happens in this step

arr[0] = 1

noDeletion = 1
oneDeletion = 0  (not a real run yet — no deletion has happened)
best = 1

Seed noDeletion with the first element; oneDeletion starts at its initial 0 but represents no run yet.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function maximumSum(arr) {
  let noDeletion = arr[0];
  let oneDeletion = 0;
  let best = arr[0];

  for (let i = 1; i < arr.length; i++) {
    oneDeletion = Math.max(noDeletion, oneDeletion + arr[i]);
    noDeletion = Math.max(arr[i], noDeletion + arr[i]);
    best = Math.max(best, noDeletion, oneDeletion);
  }

  return best;
}

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

6. Test cases

Test cases

Input	Expected	Covers
`arr = [1, -2, 0, 3]`	`4`	example from the docstring
`arr = [1, -2, -2, 3]`	`3`	deleting one element is not enough to beat just taking the single best element
`arr = [-1, -1, -1, -1]`	`-1`	every value negative — the deletion can never help reach a positive sum
`arr = [7]`	`7`	smallest valid input — no deletion is possible without emptying the subarray
`arr = [2, 3]`	`5`	both elements are worth keeping, the deletion is never used
`arr = [3, -2, -4, 5]`	`6`	deleting the worse of two negative dips beats every deletion-free subarray
`arr = [-5, -5, -5]`	`-5`	repeated equal negative values, deletion cannot turn the answer positive

Maximum Subarray Sum with One Deletion