Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1186. Maximum Subarray Sum with One Deletion - Leetcode Solution

Code Implementation

class Solution:
    def maximumSum(self, arr):
        n = len(arr)
        if n == 0:
            return 0
        max_end_here_no_del = arr[0]
        max_end_here_one_del = float('-inf')
        max_so_far = arr[0]
        for i in range(1, n):
            max_end_here_one_del = max(max_end_here_no_del, max_end_here_one_del + arr[i])
            max_end_here_no_del = max(arr[i], max_end_here_no_del + arr[i])
            max_so_far = max(max_so_far, max_end_here_no_del, max_end_here_one_del)
        return max_so_far
      
class Solution {
public:
    int maximumSum(vector<int>& arr) {
        int n = arr.size();
        int max_end_here_no_del = arr[0];
        int max_end_here_one_del = INT_MIN;
        int max_so_far = arr[0];
        for (int i = 1; i < n; ++i) {
            max_end_here_one_del = max(max_end_here_no_del, max_end_here_one_del + arr[i]);
            max_end_here_no_del = max(arr[i], max_end_here_no_del + arr[i]);
            max_so_far = max(max_so_far, max_end_here_no_del);
            max_so_far = max(max_so_far, max_end_here_one_del);
        }
        return max_so_far;
    }
};
      
class Solution {
    public int maximumSum(int[] arr) {
        int n = arr.length;
        int maxEndHereNoDel = arr[0];
        int maxEndHereOneDel = Integer.MIN_VALUE;
        int maxSoFar = arr[0];
        for (int i = 1; i < n; i++) {
            maxEndHereOneDel = Math.max(maxEndHereNoDel, maxEndHereOneDel + arr[i]);
            maxEndHereNoDel = Math.max(arr[i], maxEndHereNoDel + arr[i]);
            maxSoFar = Math.max(maxSoFar, Math.max(maxEndHereNoDel, maxEndHereOneDel));
        }
        return maxSoFar;
    }
}
      
var maximumSum = function(arr) {
    let n = arr.length;
    let maxEndHereNoDel = arr[0];
    let maxEndHereOneDel = -Infinity;
    let maxSoFar = arr[0];
    for (let i = 1; i < n; i++) {
        maxEndHereOneDel = Math.max(maxEndHereNoDel, maxEndHereOneDel + arr[i]);
        maxEndHereNoDel = Math.max(arr[i], maxEndHereNoDel + arr[i]);
        maxSoFar = Math.max(maxSoFar, maxEndHereNoDel, maxEndHereOneDel);
    }
    return maxSoFar;
};

Problem Description

The task is to find the maximum sum of a non-empty subarray of an integer array arr, where you may optionally delete at most one element in the subarray (but you do not have to delete any). The subarray must remain non-empty after deletion. The goal is to return the largest sum possible under these rules.

Key constraints:
  • You may delete at most one element from the subarray, but deletion is optional.
  • The subarray must be contiguous and non-empty after deletion.
  • Each element in arr can be used at most once per subarray.
  • There is always at least one valid subarray (since the array is non-empty).

Thought Process

When first encountering this problem, it seems similar to the classic "Maximum Subarray Sum" (Kadane's Algorithm). The twist is the option to delete a single element, which increases the complexity.

A brute-force approach would consider every possible subarray and, for each, try deleting every possible element. However, this would be too slow for large arrays.

To optimize, we need to track not just the best sum ending at each position, but also the best sum ending at each position if we've already deleted one element. This leads to the idea of using dynamic programming to track two states as we scan the array: one where we haven't deleted, and one where we have.

Solution Approach

The optimal solution uses a dynamic programming approach inspired by Kadane's Algorithm.

  1. Define two states:
    • max_end_here_no_del: The maximum sum subarray ending at the current index without any deletion.
    • max_end_here_one_del: The maximum sum subarray ending at the current index with one deletion already performed.
  2. Initialization:
    • Set max_end_here_no_del to arr[0] (since the subarray must be non-empty).
    • Set max_end_here_one_del to negative infinity or a very small value (since we can't delete before index 0).
    • Set max_so_far to arr[0].
  3. Iterate through the array:
    • For each index i (starting from 1), update the two states:
      • max_end_here_one_del = max(max_end_here_no_del, max_end_here_one_del + arr[i])
      • max_end_here_no_del = max(arr[i], max_end_here_no_del + arr[i])
    • Update max_so_far as the maximum of itself, max_end_here_no_del, and max_end_here_one_del.
  4. Return max_so_far as the answer.

Why this works:
  • At each step, max_end_here_no_del is just standard Kadane's.
  • max_end_here_one_del considers either deleting the current element (thus taking the previous max_end_here_no_del), or extending a previous subarray where a deletion already happened.
  • This ensures that every possible single deletion is considered in O(n) time.

Example Walkthrough

Input: arr = [1, -2, 0, 3]

Let's walk through each step:
  • Start: max_end_here_no_del = 1, max_end_here_one_del = -inf, max_so_far = 1
  • i = 1, arr[1] = -2
    • max_end_here_one_del = max(1, -inf + (-2)) = 1
    • max_end_here_no_del = max(-2, 1 + (-2)) = -1
    • max_so_far = max(1, -1, 1) = 1
  • i = 2, arr[2] = 0
    • max_end_here_one_del = max(-1, 1 + 0) = 1
    • max_end_here_no_del = max(0, -1 + 0) = 0
    • max_so_far = max(1, 0, 1) = 1
  • i = 3, arr[3] = 3
    • max_end_here_one_del = max(0, 1 + 3) = 4
    • max_end_here_no_del = max(3, 0 + 3) = 3
    • max_so_far = max(1, 3, 4) = 4
Result: The maximum subarray sum with at most one deletion is 4 (delete -2, sum [1,0,3]).

Time and Space Complexity

  • Brute-force approach:
    • Try all subarrays (O(n2)), and for each, try deleting each element (O(n)).
    • Total: O(n3)
  • Optimized DP approach (this solution):
    • Single pass through array: O(n)
    • Constant extra space for variables (O(1))
    • Total: O(n) time, O(1) space
This efficiency is achieved by tracking only two variables per iteration and updating them in constant time.

Summary

The "Maximum Subarray Sum with One Deletion" problem extends the classic Kadane's Algorithm by allowing a single optional deletion. By maintaining two running totals—one for the case with no deletions, and one for the case with one deletion—we can efficiently compute the answer in a single pass. This dynamic programming approach ensures all possible deletions are considered without redundant computation, making the solution both elegant and highly efficient.