Maximum Subarray Sum with One Deletion

Medium
1135.

Maximum Subarray Sum with One Deletion

Maximum Subarray Sum with One Deletion is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Microsoft and Two Sigma interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var maximumSum = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Subarray Sum with One Deletion — Problem & Solution

Maximum Subarray Sum with One Deletion solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Subarray Sum with One Deletion is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Microsoft and Two Sigma interviews.

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

Hints for Maximum Subarray Sum with One Deletion

  1. Hint 1

    Start from Kadane's algorithm: the best subarray sum ending at each index.

  2. Hint 2

    Add a second state: the best sum of a subarray ending at i from which exactly one element has been deleted.

  3. Hint 3

    withDel[i] = max(withDel[i-1] + arr[i], keep[i-1]) — either the deletion happened earlier, or arr[i] itself is the deleted element.

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)

Java

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

C++

int maximumSum(vector<int>& arr) {
    int keep = arr[0], del = -1000000000, best = arr[0];
    for (size_t i = 1; i < arr.size(); i++) {
        int a = arr[i];
        int newDel = max(del + a, keep);
        keep = max(keep + a, a);
        del = newDel;
        best = max(best, max(keep, del));
    }
    return 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming