Maximum Subarray Sum with One Deletion Interview Question for Amazon

Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.

Note that the subarray needs to be non-empty after deleting one element.

Example 1:

Input: arr = [1,-2,0,3]
Output: 4
Explanation: Because we can choose [1, -2, 0, 3] and drop -2, thus the subarray [1, 0, 3] becomes the maximum value.

Example 2:

Input: arr = [1,-2,-2,3]
Output: 3
Explanation: We just choose [3] and it's the maximum sum.

Example 3:

Input: arr = [-1,-1,-1,-1]
Output: -1
Explanation: The final subarray needs to be non-empty. You can't choose [-1] and delete -1 from it, then get an empty subarray to make the sum equals to 0.

Constraints:

1 <= arr.length <= 10^5
-10^4 <= arr[i] <= 10^4

Maximum Subarray Sum with One Deletion

Problem

Given an array of integers, find the maximum possible sum of a non-empty subarray after deleting at most one element. The subarray must contain at least one element after the optional deletion.

Brute Force Approach

Iterate through all possible subarrays.
For each subarray, iterate through each element and consider deleting it.
Calculate the sum of the remaining elements after deletion.
Keep track of the maximum sum encountered.

Code (Python):

def max_subarray_sum_brute_force(arr):
    max_sum = float('-inf')
    n = len(arr)

    for i in range(n):
        for j in range(i, n):
            # Consider the subarray arr[i:j+1]
            subarray = arr[i:j+1]
            
            # If subarray has only one element, just consider it
            if len(subarray) == 1:
                max_sum = max(max_sum, subarray[0])
                continue

            # Consider deleting each element
            for k in range(len(subarray)):
                temp_subarray = subarray[:k] + subarray[k+1:]
                current_sum = sum(temp_subarray)
                max_sum = max(max_sum, current_sum)
                
    return max_sum

Time Complexity: O(n³). The nested loops to find all subarrays take O(n²), and for each subarray, deleting an element and calculating the sum takes O(n).

Space Complexity: O(n) due to creating subarrays.

Optimal Approach (Dynamic Programming)

We can use dynamic programming to solve this problem more efficiently.

Create two arrays, left and right, where:
- left[i] stores the maximum subarray sum ending at index i without any deletion.
- right[i] stores the maximum subarray sum starting from index i without any deletion.
Create an array with_deletion such that with_deletion[i] represents the maximum subarray sum with one deletion happening at index i.
Calculate the overall maximum sum by considering:
- Maximum value in left array (no deletion).
- Maximum value of left[i-1] + right[i+1] for each index i (deletion at index i).

Code (Python):

def max_subarray_sum(arr):
    n = len(arr)
    left = [0] * n
    right = [0] * n
    
    # Calculate left[i]
    left[0] = arr[0]
    max_so_far = arr[0]
    for i in range(1, n):
        left[i] = max(arr[i], left[i-1] + arr[i])
        max_so_far = max(max_so_far, left[i])
        
    # Calculate right[i]
    right[n-1] = arr[n-1]
    for i in range(n-2, -1, -1):
        right[i] = max(arr[i], right[i+1] + arr[i])

    # Calculate max sum with one deletion
    max_sum = max_so_far
    for i in range(1, n - 1):
        max_sum = max(max_sum, left[i-1] + right[i+1])
    
    #Consider the case when array has only one element
    if n == 1:
        return arr[0]
    
    return max_sum

Explanation:

The left array is built using Kadane's algorithm to find the maximum subarray sum ending at each index.
Similarly, the right array is built to find the maximum subarray sum starting from each index.
The loop calculates the maximum sum by potentially deleting an element at each index i and adding the maximum sum to the left of i and the maximum sum to the right of i.

Time Complexity: O(n). We iterate through the array three times.

Space Complexity: O(n). We use two arrays, left and right, of size n.

Edge Cases

Empty array: The problem states that the array is non-empty, so we don't need to handle this.
Array with one element: Return the element itself.
Array with all negative numbers: The algorithm correctly finds the maximum single element.

Maximum Subarray Sum with One Deletion

Solution

Maximum Subarray Sum with One Deletion

Problem

Brute Force Approach

Optimal Approach (Dynamic Programming)

Edge Cases