Get started

Maximum Subarray Sum with One Deletion — Medium Problem & Solution

Choose a non-empty contiguous subarray of arr, then optionally delete at most one element from it.

Problem statement

Choose a non-empty contiguous subarray of arr, then optionally delete at most one element from it. The subarray must still contain at least one element after the deletion.

Return the maximum possible sum of the remaining elements.

Example 1

Input: arr = [2,-5,3,4]
Output: 9
Explanation: Take the whole array and delete `-5`.

Example 2

Input: arr = [-3,-1,-4]
Output: -1
Explanation: The best is the single element `-1`; deleting it would leave nothing.

Example 3

Input: arr = [6,-1,-1,6]
Output: 11
Explanation: Delete one of the `-1`s: `6 - 1 + 6`.

Constraints

  • 1 <= arr.length <= 10^5
  • -10^4 <= arr[i] <= 10^4

How to solve Maximum Subarray Sum with One Deletion

Run Kadane's algorithm with two states per index: no deletion yet, and exactly one deletion already used.

Approach

  1. Let keep be the best sum of a subarray ending at the current index with no deletion, and del the best with one deletion. Start with keep = arr[0], del = -infinity, best = arr[0].
  2. For each later element a: newDel = max(del + a, keep) (extend a deleted run, or delete a itself after a non-empty run).
  3. keep = max(keep + a, a) (plain Kadane).
  4. Set del = newDel and best = max(best, keep, del).
  5. Return best.

Why it works

Every candidate subarray ending at i either uses no deletion (covered by Kadane) or deletes one element; if the deleted element is arr[i] the rest is a non-empty no-deletion subarray ending at i - 1, and otherwise it is a one-deletion subarray ending at i - 1 extended by arr[i]. Both cases are exactly the two terms of the recurrence.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Deleting the only element of a single-element subarray is not allowed — del must start at minus infinity, not 0.
  • When every value is negative the answer is the largest single element.
  • Compute the new del from the old keep before overwriting it.

Reference solution

Python

from typing import List

def maximumSum(arr: List[int]) -> int:
    keep = arr[0]
    dele = float("-inf")
    best = arr[0]
    for a in arr[1:]:
        new_del = max(dele + a, keep)
        keep = max(keep + a, a)
        dele = new_del
        best = max(best, keep, dele)
    return int(best)

JavaScript

var maximumSum = function(arr) {
    var keep = arr[0], del = -1000000000, best = arr[0];
    for (var i = 1; i < arr.length; i++) {
        var a = arr[i];
        var newDel = Math.max(del + a, keep);
        keep = Math.max(keep + a, a);
        del = newDel;
        best = Math.max(best, keep, del);
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming