Watch 10 video solutions for Maximum Subarray Sum with One Deletion, a medium level problem involving Array, Dynamic Programming. This walkthrough by Kelvin Chandra has 5,994 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105-104 <= arr[i] <= 104Problem Overview: Given an integer array, find the maximum subarray sum where you are allowed to delete at most one element from the chosen subarray. The subarray must remain non-empty after the deletion. This is a variation of the classic maximum subarray (Kadane’s algorithm) with an additional decision: keep the current element or remove one element to potentially improve the sum.
Approach 1: Dynamic Programming with Two Arrays (O(n) time, O(n) space)
This approach keeps two dynamic programming arrays. forward[i] stores the maximum subarray sum ending at index i without any deletion, computed using the standard Kadane transition. backward[i] stores the maximum subarray sum starting at index i. After filling both arrays with linear scans, you try deleting each element i and combine the best subarray ending at i-1 with the best starting at i+1. The result for deleting i becomes forward[i-1] + backward[i+1]. The final answer is the maximum of the normal Kadane result and all deletion candidates. This method is easy to reason about because it explicitly models both directions of the subarray using array traversal and dynamic programming states.
Approach 2: Optimized Dynamic Programming (Kadane Variant) (O(n) time, O(1) space)
You can compress the previous idea into two running states instead of full arrays. Track noDelete, the maximum subarray sum ending at the current index with no deletion, and oneDelete, the maximum sum ending at the current index with exactly one deletion already used. For each element, update oneDelete as the maximum of deleting the current element (noDelete) or extending a previous deleted state (oneDelete + arr[i]). Update noDelete using the classic Kadane step: max(arr[i], noDelete + arr[i]). Keep a global maximum across both states. This maintains the same logic as the two-array solution but compresses the DP into constant memory. It’s essentially an extension of Kadane’s algorithm tailored for one optional removal.
The key insight: deletion lets you skip one negative element that would normally break a profitable subarray. Instead of recomputing sums for every possible removal, dynamic programming tracks the best sums with and without using that deletion.
Recommended for interviews: The optimized dynamic programming approach is what most interviewers expect. It shows you understand Kadane’s algorithm and can extend it with additional state. The two-array method is still valuable because it clearly demonstrates the transition logic and helps derive the constant-space solution. Both rely on core ideas from array processing and dynamic programming patterns commonly tested in technical interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Two Arrays | O(n) | O(n) | When you want a clear and intuitive DP formulation that explicitly tracks prefix and suffix subarray sums. |
| Optimized Dynamic Programming (Kadane Variant) | O(n) | O(1) | Best for interviews and production code where memory efficiency matters. |