Problem Description

You are given an array of integers and need to find the maximum sum of a non-empty subarray (contiguous elements) where you can optionally delete at most one element from the subarray.

The key requirements are:

• The subarray must contain contiguous elements from the original array
• You can choose to delete either 0 or 1 element from your chosen subarray
• After any deletion, the subarray must still be non-empty (contain at least one element)
• You want to maximize the sum of the remaining elements

For example, if you have the array [1, -2, 0, 3]:

• You could choose the subarray [1, -2, 0, 3] and delete -2 to get sum = 1 + 0 + 3 = 4
• You could choose the subarray [0, 3] without deleting anything to get sum = 0 + 3 = 3
• You could choose just [3] without deleting anything to get sum = 3

The goal is to find the maximum possible sum among all valid choices of subarrays and deletion options.

Intuition

When thinking about this problem, we need to consider two scenarios: either we don't delete any element, or we delete exactly one element from our subarray.

If we don't delete any element, this becomes the classic maximum subarray sum problem (Kadane's algorithm), where we find the contiguous subarray with the largest sum.

The interesting part is when we delete one element. If we delete element at position i, we're essentially connecting two separate subarrays: one that ends right before position i, and another that starts right after position i. The sum would be the maximum subarray ending at position i-1 plus the maximum subarray starting at position i+1.

This observation leads us to think about preprocessing: What if we could know, for each position, the maximum subarray sum ending at that position? And similarly, the maximum subarray sum starting from that position?

We can build two arrays:

• left[i]: stores the maximum subarray sum ending at position i
• right[i]: stores the maximum subarray sum starting at position i

For left[i], we use the logic: either extend the previous maximum subarray by including arr[i], or start fresh from arr[i] if the previous sum was negative. This gives us left[i] = max(left[i-1], 0) + arr[i].

Similarly, right[i] can be computed by traversing from right to left.

Once we have these arrays, finding the answer becomes straightforward:

• Maximum without deletion: max(left[i]) for all i
• Maximum with one deletion at position i: left[i-1] + right[i+1]

We take the maximum of all these possibilities to get our final answer.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses preprocessing combined with enumeration to find the maximum sum.

Step 1: Build the left array

We traverse the array from left to right, computing the maximum subarray sum ending at each position using Kadane's algorithm:

s = 0
for i, x in enumerate(arr):
    s = max(s, 0) + x
    left[i] = s

For each position i, we decide whether to extend the previous subarray (s) or start fresh. If s is negative, we reset it to 0 before adding the current element x. This ensures left[i] contains the maximum sum of any subarray ending at position i.

Step 2: Build the right array

Similarly, we traverse the array from right to left to compute the maximum subarray sum starting at each position:

s = 0
for i in range(n - 1, -1, -1):
    s = max(s, 0) + arr[i]
    right[i] = s

This gives us right[i] as the maximum sum of any subarray starting at position i.

Step 3: Find the maximum sum without deletion

The maximum subarray sum without any deletion is simply the maximum value in the left array:

ans = max(left)

Step 4: Consider deleting one element

For each possible deletion position i (from index 1 to n-2, since we need at least one element on each side), we calculate the sum of connecting the maximum subarray ending at i-1 with the maximum subarray starting at i+1:

for i in range(1, n - 1):
    ans = max(ans, left[i - 1] + right[i + 1])

We skip positions 0 and n-1 because deleting them wouldn't connect two subarrays—it would just truncate one end.

Step 5: Return the result

The final answer is the maximum value found across all scenarios (with or without deletion).

The time complexity is O(n) for building both arrays and O(n) for finding the maximum, giving us O(n) overall. The space complexity is O(n) for the two auxiliary arrays.

Example Walkthrough

Let's walk through the solution with the array [2, -1, 3, -2, 4].

Step 1: Build the left array (max subarray sum ending at each position)

Starting with s = 0:

• Position 0: s = max(0, 0) + 2 = 2, so left[0] = 2
• Position 1: s = max(2, 0) + (-1) = 1, so left[1] = 1
• Position 2: s = max(1, 0) + 3 = 4, so left[2] = 4
• Position 3: s = max(4, 0) + (-2) = 2, so left[3] = 2
• Position 4: s = max(2, 0) + 4 = 6, so left[4] = 6

Result: left = [2, 1, 4, 2, 6]

Step 2: Build the right array (max subarray sum starting at each position)

Starting from the right with s = 0:

• Position 4: s = max(0, 0) + 4 = 4, so right[4] = 4
• Position 3: s = max(4, 0) + (-2) = 2, so right[3] = 2
• Position 2: s = max(2, 0) + 3 = 5, so right[2] = 5
• Position 1: s = max(5, 0) + (-1) = 4, so right[1] = 4
• Position 0: s = max(4, 0) + 2 = 6, so right[0] = 6

Result: right = [6, 4, 5, 2, 4]

Step 3: Find maximum without deletion

Maximum of left array = max([2, 1, 4, 2, 6]) = 6

This corresponds to the subarray [2, -1, 3, -2, 4] with sum 6.

Step 4: Consider deleting one element

For each possible deletion position (indices 1 to 3):

• Delete index 1 (element -1): left[0] + right[2] = 2 + 5 = 7
  • This connects subarray [2] with subarray [3, -2, 4]
• Delete index 2 (element 3): left[1] + right[3] = 1 + 2 = 3
  • This connects subarray [2, -1] with subarray [-2, 4]
• Delete index 3 (element -2): left[2] + right[4] = 4 + 4 = 8
  • This connects subarray [2, -1, 3] with subarray [4]

Step 5: Return the result

Maximum value found = max(6, 7, 3, 8) = 8

The optimal solution is to choose the entire array [2, -1, 3, -2, 4] and delete the element at index 3 (value -2), giving us [2, -1, 3, 4] with sum = 8.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array arr. This is because:

• The first loop iterates through all n elements to build the left array: O(n)
• The second loop iterates through all n elements in reverse to build the right array: O(n)
• Finding the maximum of the left array takes O(n)
• The final loop iterates through n-2 elements to find the maximum sum: O(n)
• Total: O(n) + O(n) + O(n) + O(n) = O(n)

The space complexity is O(n), where n is the length of the array arr. This is because:

• The left array stores n elements: O(n)
• The right array stores n elements: O(n)
• Other variables (s, ans, i, x) use constant space: O(1)
• Total: O(n) + O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly handling arrays with all negative numbers

The Issue: When the array contains only negative numbers, the standard Kadane's algorithm implementation shown in the code will produce incorrect results. The line current_sum = max(current_sum, 0) + arr[i] will reset to 0 whenever the sum becomes negative, which means for an all-negative array, each left[i] and right[i] will just equal arr[i] itself.

However, the real problem occurs when trying to delete an element. If we have [-1, -2, -3] and delete -3, the code calculates left[1] + right[3] (which is out of bounds) or similar invalid connections. More critically, when all numbers are negative, deleting the most negative number should give us the best sum, but the current approach might not handle this correctly.

Example of the problem:

arr = [-2, -1, -3]
# After building arrays:
# left = [-2, -1, -3]
# right = [-1, -1, -3]
# max(left) = -1 (correct for no deletion)
# But when considering deletion at index 1:
# left[0] + right[2] = -2 + (-3) = -5
# This gives us -5 when we should get -2 (deleting -3 from [-2, -3])

The Fix: We need to ensure that when connecting subarrays after deletion, both sides are actually valid maximum subarrays, not just individual elements. Additionally, we need special handling to ensure we're considering the case where deleting an element from a subarray of length 2 gives us just one element:

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        if n == 1:
            return arr[0]
      
        # dp[i][0] = max subarray sum ending at i without deletion
        # dp[i][1] = max subarray sum ending at i with at most one deletion
        dp = [[float('-inf')] * 2 for _ in range(n)]
      
        dp[0][0] = arr[0]
        dp[0][1] = 0  # Can't delete from a single element and have non-empty result
      
        result = arr[0]
      
        for i in range(1, n):
            # Without deletion
            dp[i][0] = max(arr[i], dp[i-1][0] + arr[i])
          
            # With deletion - either delete current element or keep it
            dp[i][1] = max(
                dp[i-1][0],  # Delete current element
                dp[i-1][1] + arr[i]  # Already deleted something before
            )
          
            result = max(result, dp[i][0], dp[i][1])
      
        return result

Pitfall 2: Edge case with single element array

The Issue: The original code doesn't explicitly handle the case where the array has only one element. When n = 1, the loop for i in range(1, n - 1) doesn't execute at all (since range(1, 0) is empty), which is actually fine. However, the code becomes harder to understand and verify for correctness.

The Fix: Add an explicit check at the beginning:

if n == 1:
    return arr[0]

Pitfall 3: Misunderstanding what constitutes a valid deletion

The Issue: The code only considers deleting elements at positions 1 through n-2, assuming we're always connecting two non-empty subarrays. However, we might want to delete the first or last element of our chosen subarray, which would mean we're not "connecting" anything but rather just taking a shorter subarray.

Example: For array [5, -10, 2], the optimal solution might be to take subarray [5, -10] and delete -10, giving us just [5]. The current approach wouldn't consider this case properly.

The Fix: Use dynamic programming that tracks both scenarios (with and without deletion) more explicitly, as shown in the solution for Pitfall 1. This approach naturally handles all deletion cases including edge deletions.