Jobs

Interviews

Discussions

Maximum Subarray Sum with One Deletion

Medium

Google

2 views

Topics:

ArraysDynamic Programming

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⁵
-10⁴ <= arr[i] <= 10⁴

Maximum Subarray Sum with One Deletion

Medium

Google

2 views

Topics:

ArraysDynamic Programming

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⁵
-10⁴ <= arr[i] <= 10⁴

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array? Can I expect negative numbers, zero, or only positive integers?
What should I return if the array is empty or null?
If all the numbers in the array are negative, should I return 0 (representing deleting the entire array), or the largest single element (i.e., the least negative number)?
Is the input array guaranteed to have at least one element?
By 'subarray,' do you mean a contiguous block of elements within the original array?

Brute Force Solution

Approach

We want to find the biggest possible total from a sequence of numbers, allowing ourselves to remove just one number. The brute force way is to check every single possibility by removing numbers one at a time and calculating the total.

Here's how the algorithm would work step-by-step:

First, find the total of the numbers without removing any.
Next, consider each number in the sequence one at a time.
For each number, imagine removing it from the sequence.
Calculate the total of the remaining numbers after the removal.
Compare this new total with the previous biggest total you've found.
If the new total is bigger, remember it as the biggest so far.
Repeat this process for every number in the sequence, each time considering removing a different number.
After checking all possible removals, the biggest total you've kept track of is the answer.

Code Implementation

def max_subarray_sum_with_one_deletion_brute_force(numbers):
    maximum_sum = sum(numbers)

    for index_to_remove in range(len(numbers)):
        # Create a new list with the element removed
        temporary_list = numbers[:index_to_remove] + numbers[index_to_remove+1:]

        # Calculate the sum of the subarray after deletion.
        current_sum = sum(temporary_list)

        # Update the maximum sum if the current sum is greater.
        maximum_sum = max(maximum_sum, current_sum)

    return maximum_sum

Big(O) Analysis

Time Complexity

O(n²) – The provided solution iterates through each of the n elements of the input array. For each of these elements, it calculates the sum of the remaining elements after removing the current element. Calculating the sum of the remaining elements requires traversing the array again, which takes O(n) time. Therefore, the overall time complexity is O(n * n), which simplifies to O(n²).

Space Complexity

O(1) – The provided brute force approach primarily involves iterating through the input array and calculating sums. It only requires a few variables to store the current sum, the maximum sum found so far, and potentially an index for iteration. No auxiliary data structures like arrays, hash maps, or recursion are used that grow with the input size N (where N is the number of elements in the input sequence). Therefore, the space complexity is constant.

Optimal Solution

Approach

The best strategy focuses on calculating two kinds of running sums as we go through the numbers. One sum keeps track of the largest subarray sum we've seen so far without deleting anything. The other keeps track of the largest subarray sum we've seen so far *with* a deletion.

Here's how the algorithm would work step-by-step:

First, calculate the maximum sum of any continuous section of the list of numbers, assuming we don't delete any numbers at all. This is like finding the best possible unbroken stretch.
Next, look at the list from left to right. For each number, calculate the maximum sum of a continuous section that *ends* at that number, assuming we might have already deleted a number somewhere before it.
Then, do the same thing but go through the list from right to left. This time, calculate the maximum sum of a continuous section that *starts* at each number, again assuming a possible earlier deletion.
Now, for each number in the list, imagine we're deleting that number. Combine the maximum sum ending at the number *before* it (calculated from left to right) with the maximum sum starting at the number *after* it (calculated from right to left). This gives us the maximum sum we can get if we delete the current number.
Compare all the maximum sums we found (the initial one without any deletion, and all the sums we calculated by deleting each number one by one). The largest of all those sums is our final answer.

Code Implementation

def maximum_subarray_sum_with_one_deletion(numbers):
    max_sum_without_deletion = float('-inf')
    current_max_sum = 0
    for number in numbers:
        current_max_sum = max(number, current_max_sum + number)
        max_sum_without_deletion = max(max_sum_without_deletion, current_max_sum)

    max_sum_ending_here = [0] * len(numbers)
    current_max_sum = 0
    for index, number in enumerate(numbers):
        current_max_sum = max(number, current_max_sum + number)
        max_sum_ending_here[index] = current_max_sum

    max_sum_starting_here = [0] * len(numbers)
    current_max_sum = 0
    for index in range(len(numbers) - 1, -1, -1):
        number = numbers[index]
        current_max_sum = max(number, current_max_sum + number)
        max_sum_starting_here[index] = current_max_sum

    max_sum_with_deletion = float('-inf')

    # Iterate and simulate deletion at each index
    for index in range(len(numbers)): 
        if index == 0:
            max_sum_with_deletion = max(max_sum_with_deletion, max_sum_starting_here[1])
        elif index == len(numbers) - 1:
            max_sum_with_deletion = max(max_sum_with_deletion, max_sum_ending_here[index - 1])
        else:
            max_sum_with_deletion = max(max_sum_with_deletion, max_sum_ending_here[index - 1] + max_sum_starting_here[index + 1])

    # Crucial: Compare sums to find the absolute maximum. 
    return max(max_sum_without_deletion, max_sum_with_deletion)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n multiple times, but each iteration involves only constant-time operations. First, we calculate the maximum subarray sum without deletions in O(n). Next, we iterate from left to right and right to left to calculate maximum subarray sums ending at and starting from each index, respectively, both in O(n). Finally, we iterate through the array again to consider deleting each element and combine the precomputed sums, also in O(n). Since all these steps are performed sequentially and are linear with respect to the input size, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm calculates the maximum subarray sum without deletion, which requires constant space. However, it also calculates maximum subarray sums ending at each index (from left to right) and starting at each index (from right to left), each potentially with a deletion. These calculations require storing intermediate sums in two auxiliary arrays, each of size N, where N is the number of elements in the input array. Therefore, the algorithm uses O(N) auxiliary space.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 as there's no subarray to sum.
Array with a single element	Return the single element's value as deleting it results in 0, which is always less than the original value.
Array with all negative numbers	Return the largest (least negative) number in the array, which is the maximum subarray after deleting all other numbers.
Array with all zeros	Return the sum of the entire array which is 0.
Array with positive and negative numbers such that the overall sum is negative, but a subarray sum is positive.	Kadane's algorithm (with and without deletion consideration) will handle finding the maximum subarray sum even when the overall sum is negative.
Integer overflow potential when summing large numbers.	Use a larger data type (e.g., long) to store the sums to prevent overflow.
Array contains MAX_INT and large negative numbers which could cause overflow after deletion.	Long data type prevents intermediate value overflow.
A very large input array.	The solution's time complexity should be O(n) to efficiently handle large arrays using dynamic programming.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array? Can I expect negative numbers, zero, or only positive integers?
What should I return if the array is empty or null?
If all the numbers in the array are negative, should I return 0 (representing deleting the entire array), or the largest single element (i.e., the least negative number)?
Is the input array guaranteed to have at least one element?
By 'subarray,' do you mean a contiguous block of elements within the original array?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, find the total of the numbers without removing any.
Next, consider each number in the sequence one at a time.
For each number, imagine removing it from the sequence.
Calculate the total of the remaining numbers after the removal.
Compare this new total with the previous biggest total you've found.
If the new total is bigger, remember it as the biggest so far.
Repeat this process for every number in the sequence, each time considering removing a different number.
After checking all possible removals, the biggest total you've kept track of is the answer.

Code Implementation

def max_subarray_sum_with_one_deletion_brute_force(numbers):
    maximum_sum = sum(numbers)

    for index_to_remove in range(len(numbers)):
        # Create a new list with the element removed
        temporary_list = numbers[:index_to_remove] + numbers[index_to_remove+1:]

        # Calculate the sum of the subarray after deletion.
        current_sum = sum(temporary_list)

        # Update the maximum sum if the current sum is greater.
        maximum_sum = max(maximum_sum, current_sum)

    return maximum_sum

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, calculate the maximum sum of any continuous section of the list of numbers, assuming we don't delete any numbers at all. This is like finding the best possible unbroken stretch.
Next, look at the list from left to right. For each number, calculate the maximum sum of a continuous section that *ends* at that number, assuming we might have already deleted a number somewhere before it.
Then, do the same thing but go through the list from right to left. This time, calculate the maximum sum of a continuous section that *starts* at each number, again assuming a possible earlier deletion.
Now, for each number in the list, imagine we're deleting that number. Combine the maximum sum ending at the number *before* it (calculated from left to right) with the maximum sum starting at the number *after* it (calculated from right to left). This gives us the maximum sum we can get if we delete the current number.
Compare all the maximum sums we found (the initial one without any deletion, and all the sums we calculated by deleting each number one by one). The largest of all those sums is our final answer.

Code Implementation

def maximum_subarray_sum_with_one_deletion(numbers):
    max_sum_without_deletion = float('-inf')
    current_max_sum = 0
    for number in numbers:
        current_max_sum = max(number, current_max_sum + number)
        max_sum_without_deletion = max(max_sum_without_deletion, current_max_sum)

    max_sum_ending_here = [0] * len(numbers)
    current_max_sum = 0
    for index, number in enumerate(numbers):
        current_max_sum = max(number, current_max_sum + number)
        max_sum_ending_here[index] = current_max_sum

    max_sum_starting_here = [0] * len(numbers)
    current_max_sum = 0
    for index in range(len(numbers) - 1, -1, -1):
        number = numbers[index]
        current_max_sum = max(number, current_max_sum + number)
        max_sum_starting_here[index] = current_max_sum

    max_sum_with_deletion = float('-inf')

    # Iterate and simulate deletion at each index
    for index in range(len(numbers)): 
        if index == 0:
            max_sum_with_deletion = max(max_sum_with_deletion, max_sum_starting_here[1])
        elif index == len(numbers) - 1:
            max_sum_with_deletion = max(max_sum_with_deletion, max_sum_ending_here[index - 1])
        else:
            max_sum_with_deletion = max(max_sum_with_deletion, max_sum_ending_here[index - 1] + max_sum_starting_here[index + 1])

    # Crucial: Compare sums to find the absolute maximum. 
    return max(max_sum_without_deletion, max_sum_with_deletion)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 as there's no subarray to sum.
Array with a single element	Return the single element's value as deleting it results in 0, which is always less than the original value.
Array with all negative numbers	Return the largest (least negative) number in the array, which is the maximum subarray after deleting all other numbers.
Array with all zeros	Return the sum of the entire array which is 0.
Array with positive and negative numbers such that the overall sum is negative, but a subarray sum is positive.	Kadane's algorithm (with and without deletion consideration) will handle finding the maximum subarray sum even when the overall sum is negative.
Integer overflow potential when summing large numbers.	Use a larger data type (e.g., long) to store the sums to prevent overflow.
Array contains MAX_INT and large negative numbers which could cause overflow after deletion.	Long data type prevents intermediate value overflow.
A very large input array.	The solution's time complexity should be O(n) to efficiently handle large arrays using dynamic programming.