#1186

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Subarray Sum with One Deletion

Find the maximum sum of a subarray with at most one deletion in this dynamic programming problem.

Problem Statement

Given an integer array, find the maximum sum of a non-empty subarray with at most one deletion. The task is to select a subarray and optionally remove one element from it, ensuring the subarray is non-empty after deletion and the remaining elements yield the maximum sum.

Note that you can only delete one element, and the final subarray must not be empty. The problem can be solved efficiently by leveraging dynamic programming to track the best subarray sum considering the deletion scenario.

Examples

Example 1

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

Output: 4

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

We just choose [3] and it's the maximum sum.

Example 3

Input: arr = [-1,-1,-1,-1]

Output: -1

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 <= 105
-104 <= arr[i] <= 104

Solution Approach

State Transition Dynamic Programming

Use dynamic programming to track two states: the maximum sum without deletion and the maximum sum with one deletion. For each element, decide whether to include it in the sum or remove the previous element, which involves maintaining two separate arrays for each state.

Handling Deletion Option

The deletion option allows for skipping one element to potentially maximize the sum. The algorithm checks whether deleting an element improves the result without making the subarray empty, ensuring an optimal solution even in cases of negative values.

Efficient Space Complexity

The problem can be solved in O(n) time with a space complexity of O(1) by storing only necessary values during the iteration, reducing the need for additional space.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(n) because we iterate through the array once. The space complexity is O(1) since we only track the current and previous states, making it space-efficient.

What Interviewers Usually Probe

Candidates should demonstrate an understanding of dynamic programming and state transitions.
Look for the candidate's ability to handle edge cases such as all negative numbers.
Candidates should be able to optimize the space complexity while maintaining the O(n) time complexity.

Common Pitfalls or Variants

Common pitfalls

Candidates may struggle to differentiate between maximum sum without deletion and with deletion.
Failing to account for cases where no deletion is optimal, especially with all negative numbers.
Misunderstanding how to maintain the subarray non-empty while deleting one element.

Follow-up variants

Modify the problem to allow multiple deletions and observe how the approach scales.
Change the input to include a mix of large positive and negative numbers, testing the ability to skip subarrays efficiently.
Ask the candidate to implement the problem with constant space complexity using only two variables for tracking the sums.

FAQ

What is the time complexity of the Maximum Subarray Sum with One Deletion problem?

The time complexity is O(n) because the solution iterates through the array once to calculate the maximum sum.

How do I solve the Maximum Subarray Sum with One Deletion if no deletions are allowed?

If no deletions are allowed, the problem reduces to the standard Maximum Subarray Sum problem, which can be solved using Kadane's algorithm in O(n) time.

Can we solve the Maximum Subarray Sum with One Deletion problem with constant space?

Yes, by maintaining only the necessary state variables (e.g., current maximum sum, previous values), we can solve the problem with constant space.

What is the main challenge of the Maximum Subarray Sum with One Deletion problem?

The main challenge is deciding when and which element to delete in order to maximize the sum while ensuring the subarray remains non-empty.

How can I optimize the solution to the Maximum Subarray Sum with One Deletion problem?

To optimize the solution, use dynamic programming to track both the maximum sum without any deletion and the maximum sum with one deletion, reducing space complexity.

terminal

Solution

Solution 1: Preprocessing + Enumeration

We can preprocess the array $\textit{arr}$ to find the maximum subarray sum ending and starting with each element, storing them in arrays $\textit{left}$ and $\textit{right}$, respectively.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        left = [0] * n
        right = [0] * n
        s = 0
        for i, x in enumerate(arr):
            s = max(s, 0) + x
            left[i] = s
        s = 0
        for i in range(n - 1, -1, -1):
            s = max(s, 0) + arr[i]
            right[i] = s
        ans = max(left)
        for i in range(1, n - 1):
            ans = max(ans, left[i - 1] + right[i + 1])
        return ans

Continue Practicing

#1187 make array strictly increasing #1191 k concatenation maximum sum #1162 as far from land as possible