We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Subarray Sum with One Deletion

Number: 1288

Difficulty: Medium

Paid? No

Companies: Amazon, Meta, Google, Two Sigma

Problem Description

Given an array of integers, determine the maximum sum for a non-empty subarray where you are allowed to delete at most one element (and the resulting subarray must still be non-empty). The goal is to choose a contiguous subarray and optionally remove one element to maximize the total sum.

Key Insights

  • Use dynamic programming to track two states: the maximum subarray sum ending at index i without deletion, and the maximum subarray sum ending at index i with one deletion.
  • The state with no deletion uses the classic Kadane’s algorithm.
  • For the state with one deletion, either use the current element added to a previously "one-deleted" state or delete the current element by taking the previous "no deletion" sum.
  • Careful handling is required when all numbers are negative, in which case no deletion might yield the maximum sum.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n) (Can be reduced to O(1) with optimized variables)

Solution

We solve this problem using dynamic programming with two arrays/variables. One (dp_no_del) tracks the maximum subarray sum ending at the current index without any deletion, while the other (dp_del) tracks the maximum subarray sum ending at the current index with one deletion allowed.

At each index:

  • For dp_no_del: We either continue the previous subarray or start a new subarray with the current element.
  • For dp_del: We either delete the current element (thus carry over the previous dp_no_del) or add the current element to the previous dp_del.

The answer is the maximum value found in both dp_no_del and dp_del across all indices.

Code Solutions

# Python solution for Maximum Subarray Sum with One Deletion

def maximumSum(arr):
    n = len(arr)
    # Initialize dp arrays
    dp_no_del = [0] * n  # Maximum subarray sum ending here without deletion
    dp_del = [0] * n     # Maximum subarray sum ending here with one deletion

    dp_no_del[0] = arr[0]
    dp_del[0] = 0  # Cannot delete the first element (subarray must be non-empty)

    max_sum = arr[0]

    # Iterate through the array, updating dp values
    for i in range(1, n):
        # Maximum no deletion: either extend the previous subarray or start fresh
        dp_no_del[i] = max(arr[i], dp_no_del[i-1] + arr[i])
        # Maximum with one deletion: either delete current element using previous dp_no_del,
        # or extend a subarray that already had one deletion
        dp_del[i] = max(dp_no_del[i-1], dp_del[i-1] + arr[i])
        # Update overall maximum sum considering both states
        max_sum = max(max_sum, dp_no_del[i], dp_del[i])

    return max_sum

# Example usage:
print(maximumSum([1, -2, 0, 3]))  # Expected output: 4
← Back to All Questions