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.
This approach uses dynamic programming to track two states: maximum subarray sum ending at each position without any deletions and with one deletion.
We maintain two arrays maxEnd[i] and maxEndWithDeletion[i]:
maxEnd[i]: Maximum sum subarray ending at i without deletions.maxEndWithDeletion[i]: Maximum sum subarray ending at i with one deletion.The transition relations are:
maxEnd[i] = max(arr[i], arr[i] + maxEnd[i-1])maxEndWithDeletion[i] = max(maxEnd[i-1], maxEndWithDeletion[i-1] + arr[i])The answer is the maximum value among max(maxEnd) and max(maxEndWithDeletion).
This C implementation iterates through the array updating two variables maxEnd and maxEndWithDeletion to keep track of the maximum subarray sum without and with one deletion respectively. The result is the maximum of these two values at each step.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), only constant space is used.
In this approach, instead of keeping arrays, we optimize space by only keeping track of the necessary values. We still maintain two states, maxEnd and maxEndWithDeletion, similar to the previous approach, but update them in one loop without using separate arrays.
This effectively reduces the space complexity, maintaining only the latest calculated values and previous calculated sums to determine the maximum sum possible at each step.
This C implementation simply uses integer variables to track the maximum sums without creating arrays, ensuring the solution is both time and space efficient.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), only constant space is used.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Two Arrays | Time Complexity: O(n), where n is the length of the array. |
| Optimized Dynamic Programming | Time Complexity: O(n), where n is the length of the array. |
| 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. |
1186 Maximum Subarray Sum with One Deletion • Kelvin Chandra • 5,994 views views
Watch 9 more video solutions →Practice Maximum Subarray Sum with One Deletion with our built-in code editor and test cases.
Practice on FleetCode