AlgoMaster Logo

Maximum Subarray Sum with One Deletion

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

This extends the classic Maximum Subarray problem (Kadane's algorithm) with one allowance: you may delete at most one element from your chosen subarray. Deletion is optional, so when a single negative value sits in the middle of an otherwise strong subarray, removing it can raise the total.

The subarray must be contiguous before the deletion. After the deletion, the remaining elements were originally contiguous neighbors with one removed from the middle. The result must also be non-empty, so deleting everything is not allowed.

The question is how to decide efficiently which element (if any) to delete. If we delete element arr[k], the best result combines the best subarray ending just before k with the best subarray starting just after k. That points to a dynamic programming approach that tracks two states: the best sum with no deletion used yet, and the best sum with one deletion already used.

Key Constraints:

  • 1 <= arr.length <= 10^5 → With n up to 100,000, an O(n^2) solution performs around 10^10 operations and times out. The target is O(n).
  • -10^4 <= arr[i] <= 10^4 → Values can be negative, so the answer can be negative. When every element is negative, the best choice is the single least negative element.

Approach 1: Brute Force

Intuition

Enumerate every possible subarray, and for each one try deleting each element or deleting none, then compute the sum. Track the maximum across all possibilities.

For each subarray defined by indices (i, j), compute its total sum. Then remove each element one at a time and check whether that improves the sum. The best value across all subarrays and all deletion choices is the answer.

Algorithm

  1. Initialize maxSum to negative infinity.
  2. For each starting index i from 0 to n-1:
    • For each ending index j from i to n-1:
      • Compute the sum of the subarray arr[i..j].
      • Update maxSum with this sum (no deletion case).
      • For each index k from i to j, compute the sum minus arr[k] and update maxSum (only if the subarray still has at least one element after deletion).
  3. Return maxSum.

Visualization and Code

Loading animation...

The cubic cost comes from recomputing subarray sums and deletion choices from scratch. The next approach precomputes the best subarray ending and starting at each index, so deleting element k reduces to combining two stored values.

Approach 2: Forward-Backward DP

Intuition

If we decide to delete element arr[k], we want the best subarray sum ending right before k plus the best subarray sum starting right after k. The two halves were originally part of one contiguous subarray, with element k sitting in between.

So we precompute two arrays: forward[i] gives the maximum subarray sum ending at index i (standard Kadane's, left to right), and backward[i] gives the maximum subarray sum starting at index i (Kadane's in reverse, right to left). Then the answer is the maximum of forward[i] for any i (no deletion), or forward[k-1] + backward[k+1] for any k (delete element k).

Algorithm

  1. Compute forward[i] for all i using Kadane's algorithm left to right: forward[i] = max(arr[i], forward[i-1] + arr[i]).
  2. Compute backward[i] for all i using Kadane's algorithm right to left: backward[i] = max(arr[i], backward[i+1] + arr[i]).
  3. Initialize maxSum to the maximum of all forward[i] values (no deletion case).
  4. For each index k from 1 to n-2, compute forward[k-1] + backward[k+1] and update maxSum (deletion case).
  5. Return maxSum.

Visualization and Code

Loading animation...

The time is already O(n), but the two arrays use O(n) extra space. The next approach keeps the same time and reduces space to O(1) by tracking both states in a single forward pass.

Approach 3: Single-Pass DP (Optimal)

Intuition

Instead of precomputing two full arrays, the same information fits in two running values updated as we move left to right: noDelete (maximum subarray sum ending here with no element deleted) and oneDelete (maximum subarray sum ending here with exactly one element deleted).

noDelete is standard Kadane's: either start a new subarray at arr[i], or extend the previous one. oneDelete has two options: delete arr[i] itself, which takes the previous noDelete and skips arr[i], or keep arr[i] and extend a subarray that already used its deletion, which adds arr[i] to the previous oneDelete.

One ordering detail matters: update oneDelete before noDelete, because the delete-arr[i] option reads the previous value of noDelete. Overwriting noDelete first would feed the new value into oneDelete and skip nothing.

Algorithm

  1. Initialize noDelete = arr[0], oneDelete = 0, and maxSum = arr[0].
  2. For each index i from 1 to n-1:
    • Update oneDelete = max(noDelete, oneDelete + arr[i]) (either delete arr[i] or extend a previous deletion).
    • Update noDelete = max(arr[i], noDelete + arr[i]) (standard Kadane's).
    • Update maxSum = max(maxSum, noDelete, oneDelete).
  3. Return maxSum.

Visualization and Code

Loading animation...