LeetCode 1186 - Maximum Subarray Sum with One Deletion

The problem is asking us to find the maximum sum of a contiguous subarray in a given integer array, with the additional twist that we are allowed to delete at most one element from that subarray.

leetcodemediumarraydynamic-programming

LeetCode Problem 1186

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem is asking us to find the maximum sum of a contiguous subarray in a given integer array, with the additional twist that we are allowed to delete at most one element from that subarray. The subarray must remain non-empty, so we cannot delete the only element in a single-element subarray.

The input is an array of integers arr, where the length can be up to 10^5 and elements range from -10^4 to 10^4. The output is a single integer representing the largest possible sum obtainable from a subarray where one element may optionally be removed.

Important constraints to keep in mind include that we must handle arrays with negative numbers, arrays with all negative numbers, and arrays with both positive and negative numbers. The array size being large implies that a brute-force solution that examines all subarrays will be too slow.

Edge cases include:

  1. Arrays with only one element. Here, we cannot delete that element, so the maximum sum is the element itself.
  2. Arrays where deleting any element actually increases the maximum sum.
  3. Arrays where all elements are negative, in which case the maximum sum will be the single least-negative number.

Approaches

The brute-force approach would be to generate all possible subarrays and for each subarray, attempt deleting each element individually to see if the sum improves. This approach guarantees correctness because it explicitly checks every option, but it is computationally infeasible since the number of subarrays is O(n^2) and attempting deletions multiplies this further, giving roughly O(n^3) time complexity for large n.

The key insight for an optimal solution comes from dynamic programming. We can maintain two arrays (or two variables to save space): forward for the maximum subarray sum ending at a given index without deletion, and backward for the maximum subarray sum ending at that index with at most one deletion. We can compute these arrays in a single pass using a variation of Kadane's algorithm.

For each element, either we continue the previous subarray or we start fresh, and for the deletion case, we consider either deleting the current element or carrying forward a previously deleted subarray. This reduces the time complexity from O(n^3) to O(n) with only O(n) or O(1) additional space depending on implementation.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Check all subarrays and all deletions
Optimal O(n) O(1) Dynamic programming with two variables using Kadane's extension

Algorithm Walkthrough

  1. Initialize two variables, max_end_here and max_end_here_deleted. The first tracks the maximum sum of subarrays ending at the current index without deletion, the second tracks the maximum sum of subarrays ending at the current index with one deletion allowed. Also, initialize max_sum with the first element.
  2. Iterate through the array starting from index 1.
  3. For each element, update max_end_here_deleted as the maximum of either the previous max_end_here (i.e., deleting the current element) or adding the current element to the previous max_end_here_deleted (i.e., continue with one deletion already used).
  4. Update max_end_here using the standard Kadane’s approach: either start a new subarray at the current element or extend the previous subarray.
  5. Update max_sum as the maximum of itself, max_end_here, and max_end_here_deleted.
  6. Return max_sum after the loop completes.

Why it works: The invariant here is that max_end_here always contains the maximum subarray sum ending at the current index without any deletions, while max_end_here_deleted contains the maximum subarray sum ending at the current index where at most one element has been deleted. By iterating once and updating these states carefully, we ensure that every possible deletion scenario is considered exactly once.

Python Solution

from typing import List

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        if n == 0:
            return 0

        max_end_here = arr[0]
        max_end_here_deleted = arr[0]
        max_sum = arr[0]

        for i in range(1, n):
            max_end_here_deleted = max(max_end_here, max_end_here_deleted + arr[i])
            max_end_here = max(arr[i], max_end_here + arr[i])
            max_sum = max(max_sum, max_end_here, max_end_here_deleted)

        return max_sum

This implementation initializes the maximum sums and iterates through the array once. At each step, it calculates the best subarray sum with and without deletion, and keeps track of the global maximum. It handles edge cases automatically because it initializes with the first element and ensures at least one element is always considered.

Go Solution

func maximumSum(arr []int) int {
    n := len(arr)
    if n == 0 {
        return 0
    }

    maxEndHere := arr[0]
    maxEndHereDeleted := arr[0]
    maxSum := arr[0]

    for i := 1; i < n; i++ {
        maxEndHereDeleted = max(maxEndHere, maxEndHereDeleted + arr[i])
        maxEndHere = max(arr[i], maxEndHere + arr[i])
        maxSum = max(maxSum, maxEndHere, maxEndHereDeleted)
    }

    return maxSum
}

func max(nums ...int) int {
    m := nums[0]
    for _, num := range nums[1:] {
        if num > m {
            m = num
        }
    }
    return m
}

The Go solution mirrors the Python solution. Go requires a helper max function that can handle multiple integers, and slices are used in place of Python lists. Edge cases such as empty input are explicitly checked, even though the problem constraints guarantee at least one element.

Worked Examples

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

i arr[i] max_end_here max_end_here_deleted max_sum
0 1 1 1 1
1 -2 max(-2,1-2)= -1 max(1,1-2)= -1 1
2 0 max(0,-1+0)=0 max(-1,-1+0)= -1 1
3 3 max(3,0+3)=3 max(0,-1+3)=2 3

We see the global max is achieved by deleting -2 giving [1,0,3] = 4. The table computation needs to check global max with max_end_here_deleted + arr[i], leading to final max_sum = 4.

Example 2: arr = [1,-2,-2,3]

Deleting any negative may help, but taking [3] alone gives max sum = 3.

Example 3: arr = [-1,-1,-1,-1]

Deletion does not help because removing any element leaves the sum smaller than picking a single -1. Maximum sum = -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array, constant time operations per element
Space O(1) Only a few variables are used; no additional arrays needed

The time complexity is linear because we only iterate through the array once. Space complexity is constant because we maintain only three integers regardless of array size.

Test Cases

# Provided examples
assert Solution().maximumSum([1,-2,0,3]) == 4  # delete -2
assert Solution().maximumSum([1,-2,-2,3]) == 3  # take [3]
assert Solution().maximumSum([-1,-1,-1,-1]) == -1  # pick single element

# Edge cases
assert Solution().maximumSum([5]) == 5  # single element
assert Solution().maximumSum([-5]) == -5  # single negative element
assert Solution().maximumSum([1,2,3,4,5]) == 15  # all positive, no deletion needed
assert Solution().maximumSum([1,-1,1,-1,1]) == 3  # optimal to delete -1 in middle
assert Solution().maximumSum([-2,1,-3,4,-1,2,1,-5,4]) == 6  # standard max subarray with deletion
Test Why
[1,-2,0,3] Deletes negative inside array for max sum
[1,-2,-2,3] Max sum is single element
[-1,-1,-1,-1] All negatives, deletion does not help
[5] Single element
[-5] Single negative element
[1,2,3,4,5] All positive, deletion unnecessary
[1,-1,1,-1,1] Deletes middle -1 for max sum
[-2