Maximum Subarray Sum with One Deletion (LeetCode 1186)
You get an integer array arr. Choose a subarray, a run of numbers that sit next to each other. You may delete at most one number from the subarray. After the deletion, the subarray must still hold at least one number.
Return the largest possible sum of the subarray after the optional deletion.
Worked Examples
arr = [1,-2,0,3]4[1, -2, 0, 3] and delete -2. The remaining numbers 1, 0, 3 sum to 4.arr = [1,-2,-2,3]3[3] has sum 3. Deleting one -2 still leaves another -2 in the run, so no larger sum exists.arr = [-1,-1,-1,-1]-1-1. The deletion cannot leave an empty subarray.⚖️Formal Constraints & Bounds
1 <= arr.length <= 105-104 <= arr[i] <= 104
Core Insight
A run that may delete one number has two states ending at each position: nothing deleted yet (keep) and one number deleted (drop). Deleting x turns the old keep into a drop, and any later number is added to drop, so drop must be computed from the keep that came before x.
Real-World Scenario & Production Applications
A run of daily profits where one bad day may be ignored, such as a single failed day that can be written off: the best stretch is the best sum of days after dropping at most one of them.
Step-by-Step Execution Trace Table
Trace of Example 1: arr = [1, -2, 0, 3]. keep = best = 1 and drop = -inf.
x | drop = max(keep, drop + x) | keep = max(x, keep + x) | best |
|---|---|---|---|
| -2 | max(1, -inf) = 1 | max(-2, -1) = -1 | 1 |
| 0 | max(-1, 1 + 0) = 1 | max(0, -1) = 0 | 1 |
| 3 | max(0, 1 + 3) = 4 | max(3, 3) = 3 | 4 |
At x = -2, deleting it gives drop = 1, the run [1]. At x = 3, drop = 1 + 3 = 4 extends that run to [1, 0, 3].
| 1 | keep = best = arr[0]; drop = float('-inf') |
| 2 | for x in arr[1:]: |
| 3 | drop = max(keep, drop + x) |
| 4 | keep = max(x, keep + x) |
| 5 | best = max(best, keep, drop) |
| 6 | return best |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Kadane's Algorithm keeps the best run ending here. If you may delete one number from the run, the run has two possible states: nothing is deleted yet (keep), or one number is already deleted (drop). Each new number x updates both. Deleting x itself turns the old keep into a drop.
➗ What Is Added To Kadane
Kadane's Algorithm gets one more piece of state, drop. The keep update is the unchanged Kadane step. The new line is drop = max(keep, drop + x): delete x, or add x to a run that has already deleted a number.
🔑 The Key Idea in the Code
drop is updated before keep, so it uses the keep from before x. If keep is updated first, drop would delete a number from a run that already includes x.
Updating
keepbeforedrop:dropdeletesxfrom the best run that ended beforex. Ifkeepalready includesx,dropdeletes a number from a run that containsx.Letting the deletion leave an empty subarray:
max(0, ...)indropcounts the empty subarray. When every number is negative, the answer is the largest number, not 0.Returning only the Kadane value:
best = max(best, keep)never uses the deletion, so[1, -3, 1]returns 1 instead of 2.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The maximum sum of a subarray, with at most one deletion": a best sum over contiguous runs is Kadane's Algorithm, and the deletion budget of one means the run can be in two states: before the deletion and after it.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
keep is the best sum of a subarray ending at x with nothing deleted. drop is the best sum ending at x with exactly one number deleted. Deleting x gives the old keep; deleting earlier gives drop + x. best takes keep and drop at every index.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Kadane's Algorithm and one extra state for the deletion. Keep is the best sum of a subarray ending at the current number with nothing deleted. Drop is the best sum ending there with one number deleted. For each number x, drop is the larger of keep, which deletes x itself, and drop plus x, which adds x to a run that already deleted a number. I update drop first, so it uses the keep from before x. Then keep is the usual Kadane step. Best takes both. That is one pass, order N time and order 1 space.
Complexity & Mathematical Proof
O(N)
Look at the loop. for x in arr[1:] visits each number once. Each visit updates drop, keep and best with one max each, which is constant work. That is N - 1 steps, so time is O(N).
O(1)
The code keeps three variables, keep, drop and best, whatever the length of arr is. There is no table and no recursion, so space is O(1).
Derivation Progression
for x in arr[1:] visits each number after the first once.
3 = O(1)
One max for drop, one for keep and one for best.
3(N - 1) = O(N)
Numbers times a constant amount of work.
Variable Definitions
Length of arr
Best sum of a subarray ending here with nothing deleted
Best sum of a subarray ending here with one number deleted
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): the variables keep, drop and best
O(1): one integer
Boundary Best / Worst Cases
: the loop always visits every number.
.
: the same count.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "maximum sum of a subarray", "delete at most one element". A best sum over runs is Kadane's Algorithm, and a deletion budget of one adds a second state: before the deletion and after it.
and , so a sum is at most , which fits in 32 bits. Trying every deletion inside every subarray is . One pass is .
drop starts at minus infinity. With float('-inf'), drop + x stays minus infinity in Python. In a fixed-width language, use a very negative number such as half the minimum integer, so that adding to it never overflows.
Maximum Subarray Sum with One Deletion (LeetCode 1186)
You get an integer array arr. Choose a subarray, a run of numbers that sit next to each other. You may delete at most one number from the subarray. After the deletion, the subarray must still hold at least one number.
Return the largest possible sum of the subarray after the optional deletion.
Worked Examples
arr = [1,-2,0,3]4[1, -2, 0, 3] and delete -2. The remaining numbers 1, 0, 3 sum to 4.arr = [1,-2,-2,3]3[3] has sum 3. Deleting one -2 still leaves another -2 in the run, so no larger sum exists.arr = [-1,-1,-1,-1]-1-1. The deletion cannot leave an empty subarray.⚖️Formal Constraints & Bounds
1 <= arr.length <= 105-104 <= arr[i] <= 104
Core Insight
A run that may delete one number has two states ending at each position: nothing deleted yet (keep) and one number deleted (drop). Deleting x turns the old keep into a drop, and any later number is added to drop, so drop must be computed from the keep that came before x.
Real-World Scenario & Production Applications
A run of daily profits where one bad day may be ignored, such as a single failed day that can be written off: the best stretch is the best sum of days after dropping at most one of them.
Step-by-Step Execution Trace Table
Trace of Example 1: arr = [1, -2, 0, 3]. keep = best = 1 and drop = -inf.
x | drop = max(keep, drop + x) | keep = max(x, keep + x) | best |
|---|---|---|---|
| -2 | max(1, -inf) = 1 | max(-2, -1) = -1 | 1 |
| 0 | max(-1, 1 + 0) = 1 | max(0, -1) = 0 | 1 |
| 3 | max(0, 1 + 3) = 4 | max(3, 3) = 3 | 4 |
At x = -2, deleting it gives drop = 1, the run [1]. At x = 3, drop = 1 + 3 = 4 extends that run to [1, 0, 3].
| 1 | keep = best = arr[0]; drop = float('-inf') |
| 2 | for x in arr[1:]: |
| 3 | drop = max(keep, drop + x) |
| 4 | keep = max(x, keep + x) |
| 5 | best = max(best, keep, drop) |
| 6 | return best |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Kadane's Algorithm keeps the best run ending here. If you may delete one number from the run, the run has two possible states: nothing is deleted yet (keep), or one number is already deleted (drop). Each new number x updates both. Deleting x itself turns the old keep into a drop.
➗ What Is Added To Kadane
Kadane's Algorithm gets one more piece of state, drop. The keep update is the unchanged Kadane step. The new line is drop = max(keep, drop + x): delete x, or add x to a run that has already deleted a number.
🔑 The Key Idea in the Code
drop is updated before keep, so it uses the keep from before x. If keep is updated first, drop would delete a number from a run that already includes x.
Updating
keepbeforedrop:dropdeletesxfrom the best run that ended beforex. Ifkeepalready includesx,dropdeletes a number from a run that containsx.Letting the deletion leave an empty subarray:
max(0, ...)indropcounts the empty subarray. When every number is negative, the answer is the largest number, not 0.Returning only the Kadane value:
best = max(best, keep)never uses the deletion, so[1, -3, 1]returns 1 instead of 2.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The maximum sum of a subarray, with at most one deletion": a best sum over contiguous runs is Kadane's Algorithm, and the deletion budget of one means the run can be in two states: before the deletion and after it.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
keep is the best sum of a subarray ending at x with nothing deleted. drop is the best sum ending at x with exactly one number deleted. Deleting x gives the old keep; deleting earlier gives drop + x. best takes keep and drop at every index.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Kadane's Algorithm and one extra state for the deletion. Keep is the best sum of a subarray ending at the current number with nothing deleted. Drop is the best sum ending there with one number deleted. For each number x, drop is the larger of keep, which deletes x itself, and drop plus x, which adds x to a run that already deleted a number. I update drop first, so it uses the keep from before x. Then keep is the usual Kadane step. Best takes both. That is one pass, order N time and order 1 space.
Complexity & Mathematical Proof
O(N)
Look at the loop. for x in arr[1:] visits each number once. Each visit updates drop, keep and best with one max each, which is constant work. That is N - 1 steps, so time is O(N).
O(1)
The code keeps three variables, keep, drop and best, whatever the length of arr is. There is no table and no recursion, so space is O(1).
Derivation Progression
for x in arr[1:] visits each number after the first once.
3 = O(1)
One max for drop, one for keep and one for best.
3(N - 1) = O(N)
Numbers times a constant amount of work.
Variable Definitions
Length of arr
Best sum of a subarray ending here with nothing deleted
Best sum of a subarray ending here with one number deleted
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): the variables keep, drop and best
O(1): one integer
Boundary Best / Worst Cases
: the loop always visits every number.
.
: the same count.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "maximum sum of a subarray", "delete at most one element". A best sum over runs is Kadane's Algorithm, and a deletion budget of one adds a second state: before the deletion and after it.
and , so a sum is at most , which fits in 32 bits. Trying every deletion inside every subarray is . One pass is .
drop starts at minus infinity. With float('-inf'), drop + x stays minus infinity in Python. In a fixed-width language, use a very negative number such as half the minimum integer, so that adding to it never overflows.