Skip to main content
Talentd

Maximum Subarray Sum with One Deletion - Solution & Explanation

MediumArrayDynamic Programming18 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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] <= 104

Approach Overview

Problem 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 1: Dynamic Programming with Two Arrays

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), only constant space is used.

Try this approach in the editor →

Approach 2: Optimized Dynamic Programming

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), only constant space is used.

Try this approach in the editor →

Approach 3: Preprocessing + Enumeration

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

If we do not delete any element, then the maximum subarray sum is the maximum value in left[i] or right[i]; if we delete an element, we can enumerate each position i in [1..n-2], calculate the value of left[i-1] + right[i+1], and take the maximum value.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array arr.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Two Arrays

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), only constant space is used.

Optimized Dynamic Programming

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), only constant space is used.

Preprocessing + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Two ArraysO(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.

Video Solution

Leetcode 1186 | Maximum Subarray Sum with One Deletion • Tech Traversal • 6,641 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Subarray Sum with One Deletion easy or hard?
Maximum Subarray Sum with One Deletion is considered a medium-level problem. It builds directly on Kadane’s algorithm but requires adding an extra state to represent the option of deleting one element, which makes the reasoning slightly more complex.
Maximum Subarray Sum with One Deletion Python/Java solution
Python and Java solutions typically implement the optimized dynamic programming approach. Maintain two variables for states with and without deletion and update them while scanning the array once. The implementation runs in O(n) time and uses O(1) additional space.
How to solve Maximum Subarray Sum with One Deletion in O(n)?
Iterate through the array while maintaining two variables: one for the maximum subarray sum ending at the current index without deletion and another with one deletion used. Update them using Kadane-style transitions and keep a global maximum. This dynamic programming approach processes each element once, giving O(n) time complexity.
What is the best approach for Maximum Subarray Sum with One Deletion?
The best approach is optimized dynamic programming based on Kadane’s algorithm. Track two states while iterating the array: the best subarray sum ending at the current index with no deletion and the best sum with one deletion already used. This runs in O(n) time and O(1) space and is the most common interview solution.
Is Maximum Subarray Sum with One Deletion asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at large tech companies including Google, Amazon, and Meta because it tests understanding of Kadane’s algorithm and dynamic programming state transitions. Interviewers often expect candidates to extend the classic maximum subarray solution.
What data structure is used in Maximum Subarray Sum with One Deletion?
The problem mainly uses arrays and dynamic programming states. Some implementations store prefix and suffix maximum subarray sums in arrays, while optimized versions track only a few variables to maintain running states.
What is the time complexity of Maximum Subarray Sum with One Deletion?
The optimal solution runs in O(n) time because the array is scanned once while maintaining dynamic programming states. Space complexity can be O(n) using two DP arrays or reduced to O(1) with a Kadane-style optimized approach.

Ready to solve this problem?

Practice Maximum Subarray Sum with One Deletion with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximize Subarray Sum After Removing All Occurrences of One Element

Next

Maximum Unique Subarray Sum After Deletion