How do you solve Maximum Subarray Sum with One Deletion on LeetCode?

Maximum Subarray Sum with One Deletion (LeetCode #1186) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Understanding how to maintain two states (with and without deletion) is crucial for dynamic programming problems.

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

The optimal solution for Maximum Subarray Sum with One Deletion runs in O(n) time and uses O(1) space. This complexity is linear because we only traverse the array once, maintaining a constant amount of additional space.

What is the brute force solution for Maximum Subarray Sum with One Deletion?

The brute force approach for Maximum Subarray Sum with One Deletion is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves checking every possible subarray and calculating the sum while considering the option to delete one element. This is straightforward but inefficient for larger arrays. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Maximum Subarray Sum with One Deletion?

Maximum Subarray Sum with One Deletion uses the following concepts: Array, Dynamic Programming. The recommended patterns to study are: Dynamic Programming, Kadane's Algorithm.

What are the interview tips for Maximum Subarray Sum with One Deletion?

Always clarify the problem requirements, especially around edge cases. Think aloud during the interview to show your thought process. Practice writing clean and efficient code, as readability matters.

What are common mistakes when solving Maximum Subarray Sum with One Deletion?

Failing to consider edge cases, such as arrays with negative numbers only. Not correctly updating the maximum sums during iterations.

#1186

Maximum Subarray Sum with One Deletion

Medium

ArrayDynamic ProgrammingDynamic ProgrammingKadane's Algorithm

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach uses dynamic programming to keep track of the maximum subarray sums with and without deletion, allowing us to compute the result in linear time.

⚙️

Algorithm

3 steps

1Step 1: Initialize two variables, max_sum and max_sum_with_deletion, to track the maximum sums.
2Step 2: Iterate through the array, updating max_sum to be the maximum of the current element or the current element plus the previous max_sum.
3Step 3: Update max_sum_with_deletion to be the maximum of itself or max_sum (without deletion) plus the current element.

solution.py10 lines

1def maxSumAfterOneDeletion(arr):
2    max_sum = arr[0]
3    max_sum_with_deletion = 0
4    for i in range(1, len(arr)):
5        max_sum = max(arr[i], max_sum + arr[i])
6        max_sum_with_deletion = max(max_sum_with_deletion + arr[i], max_sum)
7    return max(max_sum, max_sum_with_deletion)
8
9# Example usage
10print(maxSumAfterOneDeletion([1,-2,0,3]))  # Output: 4

ℹ

Complexity note: This complexity is linear because we only traverse the array once, maintaining a constant amount of additional space.

1Understanding how to maintain two states (with and without deletion) is crucial for dynamic programming problems.
2Recognizing that we can build on previous results helps in optimizing the solution.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.