Hi👋SpeedAlgo • Deliberate Practice & Cognitive Ergonomics for Software Engineers

An interactive algorithm mastery and technical interview preparation platform published by Hi👋WebEnterprise. Built for senior and staff software engineers preparing for rigorous coding screens at top tech companies (FAANG/MAMAA).

13 Core Algorithmic Patterns & 225 Practice Problems

  • 1. Two Pointers (16 Paradigms, 43 Problems): Opposite ends, sorted pair sums, palindrome verification, trapping rain water, 3Sum, container with most water — includes the Sliding Window and Fast & Slow Pointers paradigms (contiguous subarray invariants, longest substrings, Floyd's cycle detection, linked list middle).
  • 2. Binary Search (9 Paradigms, 14 Problems): Monotonic predicate partitioning (feasible(x)), boundary search, rotated sorted arrays, square roots, minimum ship capacity, median of two sorted arrays, matrix median on value range.
  • 3. Bit Manipulation (5 Paradigms, 11 Problems): Counting set bits, XOR cancellation, bit reversal, bitmask pairing, maximum XOR with a bitwise trie.
  • 4. Math & Geometry (8 Paradigms, 14 Problems): Sieve of Eratosthenes, integer/roman conversions, modular arithmetic, geometric simulation.
  • 5. Tree/Graph Depth-First Search (15 Paradigms, 24 Problems): Path sums, lowest common ancestor, tree diameter, validating BSTs, tree DP (House Robber III, Binary Tree Cameras).
  • 6. Tree/Graph Breadth-First Search (5 Paradigms, 12 Problems): Level-order traversals, shortest path in unweighted graphs, zig-zag traversals, rotting oranges, word ladders.
  • 7. Graphs (12 Paradigms, 22 Problems): Topological sort, cycle detection, Dijkstra's algorithm, bipartite graph validation, network delay.
  • 8. Backtracking (6 Paradigms, 14 Problems): Subsets, permutations, combinations, constraint satisfaction, pruning, N-Queens, Sudoku solver.
  • 9. Dynamic Programming (13 Paradigms, 28 Problems): Memoization vs tabulation, 0/1 knapsack, unbounded knapsack, coin change, edit distance, longest common subsequence.
  • 10. Heap / Priority Queue (9 Paradigms, 11 Problems): Running medians, top-k elements, interval scheduling, IPO, k-way merges.
  • 11. Advanced Data Structures (7 Paradigms, 17 Problems): Trie (prefix tree), Union-Find (Disjoint Set Union), LRU Cache, LFU Cache, range-sum queries with updates.
  • 12. Stack (5 Paradigms, 9 Problems): Next greater element, largest rectangle in histogram, remove k digits, decode string, min stack.
  • 13. Intervals & Greedy (2 Paradigms, 6 Problems): Merge intervals, interval scheduling, meeting rooms by sweep line, jump game.

4-Stage Deliberate Practice Framework

  1. Stage 1 (Compare & Learn): Read the pattern's mental model, loop invariant and Big-O proof, compare the pattern's template with the problem's solution side by side, and use the step-by-step debugger. The solution can also be shown in C#, Java, TypeScript, C++, Go or Rust for almost every problem.
  2. Stage 2 (Active Recall): Rebuild the solution from memory in a code editor, with an invariant checklist and optional progressive hints, and check it against a judged test suite.
  3. Stage 3 (AI Interview Coach, coming soon): A mock-interview stage still in development; for now, students go straight from Stage 2 to Stage 4.
  4. Stage 4 (Solve on Your Own): Solve a new problem on your own against a 15-minute timer; your code is graded against a test suite. Python and TypeScript run in your browser and C# runs on our server (design problems grade in Python and TypeScript).

Equipped with a spaced-repetition review hub on a fixed 7-step schedule (1 day up to 90 days), a two-pane Studio workspace, and study notes.

Pricing, Access & Commercial Terms

  • Core Curriculum: 100% Free. No credit card required.
  • Coins: New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins.
  • AI Coach: Each AI coach question costs 1-5 coins, priced by the server according to its size.
  • BYOK (Bring Your Own Key): AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK).
  • Extras: Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1).
  • Payments & Refunds: Nothing on the site is sold for money: coins can only be earned, never bought. There are no subscriptions or charges, so there is nothing to refund.
  • Platform Operator: Hi👋WebEnterprise. Support & policies at hispeedalgo.com.
Skip to main content
Hi👋SpeedAlgo

Invariant-First Algorithmic Mastery

Arena
238Items
Theory Context•Dynamic Programming

Builds on Kadane's Algorithm, which you haven’t finished yet.

P2MediumBuilt on Linear DP~4 min speedrun

Kadane's Algorithm with One Deletion (Maximum Subarray Sum with One Deletion)

Built on
Kadane's AlgorithmOne number may be deleted, so keep a second state, drop: the best sum ending here with one number deleted. Deleting x takes the old keep.
The problem

Maximum Subarray Sum with One Deletion (LC 1186)(opens leetcode.com)

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.

Example 1
Input:arr = [1,-2,0,3]
Output:4
Take [1, -2, 0, 3] and delete -2. The remaining numbers 1, 0, 3 sum to 4.

Kadane with One Deletion

keep = no deletion, drop = one deletion ➔ drop = max(keep, drop + x) before keep changes ➔ best of both
Spot it when: You need the best sum of one unbroken run of an array, where you may delete at most one number from the run.
Kadane with One Deletion
Python
1def maximum_sum(arr: list[int]) -> int:
2 """Maximum Subarray Sum with One Deletion: Kadane's Algorithm with a second state for one deleted number.
3 Time: O(N) | Space: O(1)
4 """
5 # keep: the best sum of a subarray ending at the current number with nothing deleted; drop: the same with exactly one number deleted
6 keep = best = arr[0]
7 drop = float('-inf')
8 for x in arr[1:]:
9 # 1. Delete x, Or Keep Deleting Earlier:
10 # Deleting x leaves the best run that ended just before x, so drop uses the old keep. A run that already deleted a number just adds x.
11 drop = max(keep, drop + x)
12 
13 # 2. Extend Or Start Fresh:
14 # The same rule as Kadane's Algorithm, with nothing deleted.
15 keep = max(x, keep + x)
16 
17 # 3. Track The Best:
18 # The best subarray may have deleted a number or not.
19 best = max(best, keep, drop)
20 
21 return best
Invariant: After each x, keep is the best sum of a subarray ending at x with nothing deleted, drop is the best sum of a subarray with one number deleted that ends at x, or ends just before x when x is the deleted number, and best is the largest of both seen so far.

With one allowed deletion, a run ending at x is in one of two states: nothing deleted (keep) or one number deleted (drop). Deleting x itself leaves the best run that ended just before x, and a run that already deleted a number just adds x, so drop = max(keep, drop + x). keep is the unchanged Kadane step, and best takes both states. The trap is the order: update drop before keep, because if keep changes first, drop deletes a number from a run that already holds x.

See it run

Kadane with One Deletion, step by step

keep 1 · drop -inf · best 1

keep 1 · drop 1 · best 1

keep -1 · drop 1 · best 1

keep -1 · drop 1 · best 1

keep 0 · drop 1 · best 1

keep 0 · drop 4 · best 1

keep 3 · drop 4 · best 4

keep 3 · drop 4 · best 4

Each column is one index of arr. The rows keep and drop fill in as the steps run.

  • x the number being read
  • keep the best run sum that ends at x with nothing deleted
  • old keep keep from the previous index, used to update drop first
  • drop the best run sum that ends at x with one number deleted

Start: keep = best = arr[0] = 1 and drop = -inf. No run with a deletion exists yet, because deleting the only number leaves an empty run.

First update drop, using the old keep = 1: drop = max(keep, drop + x) = max(1, -inf) = 1. Choosing keep means x = -2 is the deleted number.

Then update keep: keep = max(x, keep + x) = max(-2, -1) = -1. best = max(best, keep, drop) = 1.

First update drop, using the old keep = -1: drop = max(keep, drop + x) = max(-1, 1) = 1. Choosing keep means x = 0 is the deleted number.

Then update keep: keep = max(x, keep + x) = max(0, -1) = 0. best = max(best, keep, drop) = 1.

First update drop, using the old keep = 0: drop = max(keep, drop + x) = max(0, 4) = 4. Choosing keep means x = 3 is the deleted number.

Then update keep: keep = max(x, keep + x) = max(3, 3) = 3. best = max(best, keep, drop) = 4.

Done: best = 4. It counts the runs with no deletion (keep) and with one deletion (drop).

arr
01x
1-2
20
33
keep
1keep
drop
-infdrop
1 / 8
Gotchas1 of 3

Gotcha 1 of 3

  1. 1
    The trap

    Gotcha 1: Updating keep before drop

    Mistake
    keep = max(x, keep + x)
drop = max(keep, drop + x)
    Fix
    drop = max(keep, drop + x)
keep = max(x, keep + x)

    What happens: Deleting x must leave the best run that ended before x. If keep is updated first, keep already includes x, so drop takes keep with x in it and nothing is deleted.

    Example: Maximum Subarray Sum with One Deletion (LC 1186): arr = [1, -3, 1]
    Mistake: returns 1Fix: returns 2
  2. 2

    Gotcha 2: Letting the deletion leave an empty subarray

    Mistake
    drop = max(0, keep, drop + x)
    Fix
    drop = max(keep, drop + x)

    What happens: The subarray must still hold a number after the deletion. A 0 in the max is an empty subarray with sum 0. When every number is negative, best becomes 0 instead of the largest number.

    Example: Maximum Subarray Sum with One Deletion (LC 1186): arr = [-1, -1, -1, -1]
    Mistake: returns 0Fix: returns -1
  3. 3

    Gotcha 3: Returning only the Kadane value

    Mistake
    best = max(best, keep)
    Fix
    best = max(best, keep, drop)

    What happens: keep is plain Kadane's Algorithm and never uses the deletion. The best run with a deletion lives in drop, so best must take it.

    Example: Maximum Subarray Sum with One Deletion (LC 1186): arr = [1, -3, 1]
    Mistake: returns 1Fix: returns 2
Not this one if…
  • No number can be deleted from the run, so one running value curr is enough, as in Maximum Subarray (LC 53). See Kadane's Algorithm

Deep Dive

Why a second state is needed

In Kadane's Algorithm, a run ending at x has one best sum. Here the run may also delete one number. A run that has used its deletion and a run that has not are different situations, and they continue differently.

So the card keeps two sums for the subarrays that end at the current number. keep is the best sum with nothing deleted. drop is the best sum with one number deleted. The run must still hold at least one number after the deletion.

keep is the unchanged Kadane step. Everything this card adds is drop.

Why drop = max(keep, drop + x) is correct

Look at a run that has deleted one number, when the loop reaches x. There are two cases.

In the first case, the deleted number is x itself. Then the run is the best run that ended just before x, with nothing deleted. Its sum is the old keep.

In the second case, the deleted number is earlier. Then the run before x already used its deletion, and x is added. The sum is the old drop plus x.

The two cases cover every run with one deletion, so drop is the larger one.

In the first case, keep must be the old value, before it includes x. This is why drop is updated before keep.

The start, the empty run and best

The loop starts with keep = best = arr[0] and drop = float('-inf'). At index 0, no run with a deletion exists, because deleting the only number leaves an empty run. Minus infinity means that this state cannot be used yet.

At the next number, drop = max(keep, -inf + x) is the old keep, which is arr[0]. It is the run [arr[0]] after deleting arr[1].

The deletion is optional, so best = max(best, keep, drop) takes both states. A single number or an array with no useful deletion is still handled by keep.

Trace for arr = [1, -2, 0, 3], as x, keep, drop, best:

  • 1, 1, -inf, 1 (the start).
  • -2, -1, 1, 1.
  • 0, 0, 1, 1.
  • 3, 3, 4, 4.

The answer is 4. It is the run [1, 0, 3] after deleting -2.

The cost and a related problem

There are N states. Each does two max calls and one comparison. The time is O(N) and the space is O(1).

I compared maximum_sum with a brute force that tries every subarray and every optional deleted number, with at least one number left. They agreed on 10,000 random arrays, including all-negative arrays, arrays of one number and arrays with zeros.

Longest Subarray of 1's After Deleting One Element (LC 1493) has the same two states, but they hold lengths. There the deletion is required, so the answer is the largest drop, and not the largest of both states.

60-Second Pitch

"This is Kadane's Algorithm with a second state. keep is the best sum ending here with nothing deleted. drop is the best sum ending here with one number deleted. Deleting the current number takes the old keep. Deleting an earlier number adds x to the old drop. So drop = max(keep, drop + x), and I compute it before I update keep. drop starts at minus infinity, so a deletion never leaves an empty subarray. best takes the larger of both states. The time is O(N) and the space is O(1)."

Common Questions

Why must drop be updated before keep?

When the deleted number is x, drop takes the best run that ended before x. That is the old keep. If keep is updated first, it already includes x, so drop holds a run with nothing deleted. For [1, -3, 1], the wrong order returns 1 and the correct answer is 2.

Why does drop start at minus infinity?

At index 0, a run with a deletion would be empty, which is not allowed. Minus infinity means that this state does not exist yet. At the next number, drop becomes the old keep, which is a real run.

What is the answer when every number is negative?

The largest single number, because the subarray must keep at least one number. For [-1, -1, -1, -1], the answer is -1. A version that allows an empty run returns 0.

What is the time and space complexity?

O(N) time, because one loop updates both states. O(1) space, because only keep, drop and best exist.

How does Longest Subarray of 1's After Deleting One Element (LC 1493) differ?

The two states hold lengths. A 1 sets drop to max(keep, drop + 1) and then adds 1 to keep. A 0 sets drop to keep and resets keep to 0. The deletion is required there, so the answer is the largest drop.

SWE Reasoning

Spot it

  • The question asks for the best sum of one unbroken run of an array.
  • You may delete at most one number from the run.
  • The deletion may be a number in the middle, which a plain subarray cannot skip.
  • Plain Kadane's Algorithm fails on a small example such as [1, -3, 1].
  • One value per position is not enough, because a run with a used deletion continues differently from a run without one.

The invariant, step by step

  1. Before the loop, keep and best are arr[0], and drop is minus infinity. No run with a deletion exists yet.
  2. For each x, drop = max(keep, drop + x) runs first. It reads the old keep, which does not include x.
  3. The first choice deletes x. The second choice adds x to a run that already deleted a number.
  4. keep = max(x, keep + x) is the Kadane step with nothing deleted.
  5. best = max(best, keep, drop) keeps the largest sum of either state.
  6. After the last number, best is the answer.

Traps

  • Wrong order. If keep changes first, drop copies a run that already holds x, and nothing is deleted. For [1, -3, 1], the result is 1 instead of 2.
  • Empty run after the deletion. Adding 0 to the max of drop allows an empty subarray. For [-1, -1, -1, -1], the result is 0 instead of -1.
  • Returning only keep. This is plain Kadane's Algorithm and never uses the deletion.
  • Starting drop at 0. At index 0, deleting the only number would leave an empty run. Start with minus infinity.
  • Treating the deletion as required. In this problem, the deletion is optional, so best takes keep too.

Practice

Canonical LeetCode:Maximum Subarray Sum with One Deletion (LC 1186)Longest Subarray of 1's After Deleting One Element (LC 1493)
Theory Context•Dynamic Programming

Builds on Kadane's Algorithm, which you haven’t finished yet.

P2MediumBuilt on Linear DP~4 min speedrun

Kadane's Algorithm with One Deletion (Maximum Subarray Sum with One Deletion)

Built on
Kadane's AlgorithmOne number may be deleted, so keep a second state, drop: the best sum ending here with one number deleted. Deleting x takes the old keep.
The problem

Maximum Subarray Sum with One Deletion (LC 1186)(opens leetcode.com)

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.

Example 1
Input:arr = [1,-2,0,3]
Output:4
Take [1, -2, 0, 3] and delete -2. The remaining numbers 1, 0, 3 sum to 4.

Kadane with One Deletion

keep = no deletion, drop = one deletion ➔ drop = max(keep, drop + x) before keep changes ➔ best of both
Spot it when: You need the best sum of one unbroken run of an array, where you may delete at most one number from the run.
Kadane with One Deletion
Python
1def maximum_sum(arr: list[int]) -> int:
2 """Maximum Subarray Sum with One Deletion: Kadane's Algorithm with a second state for one deleted number.
3 Time: O(N) | Space: O(1)
4 """
5 # keep: the best sum of a subarray ending at the current number with nothing deleted; drop: the same with exactly one number deleted
6 keep = best = arr[0]
7 drop = float('-inf')
8 for x in arr[1:]:
9 # 1. Delete x, Or Keep Deleting Earlier:
10 # Deleting x leaves the best run that ended just before x, so drop uses the old keep. A run that already deleted a number just adds x.
11 drop = max(keep, drop + x)
12 
13 # 2. Extend Or Start Fresh:
14 # The same rule as Kadane's Algorithm, with nothing deleted.
15 keep = max(x, keep + x)
16 
17 # 3. Track The Best:
18 # The best subarray may have deleted a number or not.
19 best = max(best, keep, drop)
20 
21 return best
Invariant: After each x, keep is the best sum of a subarray ending at x with nothing deleted, drop is the best sum of a subarray with one number deleted that ends at x, or ends just before x when x is the deleted number, and best is the largest of both seen so far.

With one allowed deletion, a run ending at x is in one of two states: nothing deleted (keep) or one number deleted (drop). Deleting x itself leaves the best run that ended just before x, and a run that already deleted a number just adds x, so drop = max(keep, drop + x). keep is the unchanged Kadane step, and best takes both states. The trap is the order: update drop before keep, because if keep changes first, drop deletes a number from a run that already holds x.

See it run

Kadane with One Deletion, step by step

keep 1 · drop -inf · best 1

keep 1 · drop 1 · best 1

keep -1 · drop 1 · best 1

keep -1 · drop 1 · best 1

keep 0 · drop 1 · best 1

keep 0 · drop 4 · best 1

keep 3 · drop 4 · best 4

keep 3 · drop 4 · best 4

Each column is one index of arr. The rows keep and drop fill in as the steps run.

  • x the number being read
  • keep the best run sum that ends at x with nothing deleted
  • old keep keep from the previous index, used to update drop first
  • drop the best run sum that ends at x with one number deleted

Start: keep = best = arr[0] = 1 and drop = -inf. No run with a deletion exists yet, because deleting the only number leaves an empty run.

First update drop, using the old keep = 1: drop = max(keep, drop + x) = max(1, -inf) = 1. Choosing keep means x = -2 is the deleted number.

Then update keep: keep = max(x, keep + x) = max(-2, -1) = -1. best = max(best, keep, drop) = 1.

First update drop, using the old keep = -1: drop = max(keep, drop + x) = max(-1, 1) = 1. Choosing keep means x = 0 is the deleted number.

Then update keep: keep = max(x, keep + x) = max(0, -1) = 0. best = max(best, keep, drop) = 1.

First update drop, using the old keep = 0: drop = max(keep, drop + x) = max(0, 4) = 4. Choosing keep means x = 3 is the deleted number.

Then update keep: keep = max(x, keep + x) = max(3, 3) = 3. best = max(best, keep, drop) = 4.

Done: best = 4. It counts the runs with no deletion (keep) and with one deletion (drop).

arr
01x
1-2
20
33
keep
1keep
drop
-infdrop
1 / 8
Gotchas1 of 3

Gotcha 1 of 3

  1. 1
    The trap

    Gotcha 1: Updating keep before drop

    Mistake
    keep = max(x, keep + x)
drop = max(keep, drop + x)
    Fix
    drop = max(keep, drop + x)
keep = max(x, keep + x)

    What happens: Deleting x must leave the best run that ended before x. If keep is updated first, keep already includes x, so drop takes keep with x in it and nothing is deleted.

    Example: Maximum Subarray Sum with One Deletion (LC 1186): arr = [1, -3, 1]
    Mistake: returns 1Fix: returns 2
  2. 2

    Gotcha 2: Letting the deletion leave an empty subarray

    Mistake
    drop = max(0, keep, drop + x)
    Fix
    drop = max(keep, drop + x)

    What happens: The subarray must still hold a number after the deletion. A 0 in the max is an empty subarray with sum 0. When every number is negative, best becomes 0 instead of the largest number.

    Example: Maximum Subarray Sum with One Deletion (LC 1186): arr = [-1, -1, -1, -1]
    Mistake: returns 0Fix: returns -1
  3. 3

    Gotcha 3: Returning only the Kadane value

    Mistake
    best = max(best, keep)
    Fix
    best = max(best, keep, drop)

    What happens: keep is plain Kadane's Algorithm and never uses the deletion. The best run with a deletion lives in drop, so best must take it.

    Example: Maximum Subarray Sum with One Deletion (LC 1186): arr = [1, -3, 1]
    Mistake: returns 1Fix: returns 2
Not this one if…
  • No number can be deleted from the run, so one running value curr is enough, as in Maximum Subarray (LC 53). See Kadane's Algorithm

Deep Dive

Why a second state is needed

In Kadane's Algorithm, a run ending at x has one best sum. Here the run may also delete one number. A run that has used its deletion and a run that has not are different situations, and they continue differently.

So the card keeps two sums for the subarrays that end at the current number. keep is the best sum with nothing deleted. drop is the best sum with one number deleted. The run must still hold at least one number after the deletion.

keep is the unchanged Kadane step. Everything this card adds is drop.

Why drop = max(keep, drop + x) is correct

Look at a run that has deleted one number, when the loop reaches x. There are two cases.

In the first case, the deleted number is x itself. Then the run is the best run that ended just before x, with nothing deleted. Its sum is the old keep.

In the second case, the deleted number is earlier. Then the run before x already used its deletion, and x is added. The sum is the old drop plus x.

The two cases cover every run with one deletion, so drop is the larger one.

In the first case, keep must be the old value, before it includes x. This is why drop is updated before keep.

The start, the empty run and best

The loop starts with keep = best = arr[0] and drop = float('-inf'). At index 0, no run with a deletion exists, because deleting the only number leaves an empty run. Minus infinity means that this state cannot be used yet.

At the next number, drop = max(keep, -inf + x) is the old keep, which is arr[0]. It is the run [arr[0]] after deleting arr[1].

The deletion is optional, so best = max(best, keep, drop) takes both states. A single number or an array with no useful deletion is still handled by keep.

Trace for arr = [1, -2, 0, 3], as x, keep, drop, best:

  • 1, 1, -inf, 1 (the start).
  • -2, -1, 1, 1.
  • 0, 0, 1, 1.
  • 3, 3, 4, 4.

The answer is 4. It is the run [1, 0, 3] after deleting -2.

The cost and a related problem

There are N states. Each does two max calls and one comparison. The time is O(N) and the space is O(1).

I compared maximum_sum with a brute force that tries every subarray and every optional deleted number, with at least one number left. They agreed on 10,000 random arrays, including all-negative arrays, arrays of one number and arrays with zeros.

Longest Subarray of 1's After Deleting One Element (LC 1493) has the same two states, but they hold lengths. There the deletion is required, so the answer is the largest drop, and not the largest of both states.

60-Second Pitch

"This is Kadane's Algorithm with a second state. keep is the best sum ending here with nothing deleted. drop is the best sum ending here with one number deleted. Deleting the current number takes the old keep. Deleting an earlier number adds x to the old drop. So drop = max(keep, drop + x), and I compute it before I update keep. drop starts at minus infinity, so a deletion never leaves an empty subarray. best takes the larger of both states. The time is O(N) and the space is O(1)."

Common Questions

Why must drop be updated before keep?

When the deleted number is x, drop takes the best run that ended before x. That is the old keep. If keep is updated first, it already includes x, so drop holds a run with nothing deleted. For [1, -3, 1], the wrong order returns 1 and the correct answer is 2.

Why does drop start at minus infinity?

At index 0, a run with a deletion would be empty, which is not allowed. Minus infinity means that this state does not exist yet. At the next number, drop becomes the old keep, which is a real run.

What is the answer when every number is negative?

The largest single number, because the subarray must keep at least one number. For [-1, -1, -1, -1], the answer is -1. A version that allows an empty run returns 0.

What is the time and space complexity?

O(N) time, because one loop updates both states. O(1) space, because only keep, drop and best exist.

How does Longest Subarray of 1's After Deleting One Element (LC 1493) differ?

The two states hold lengths. A 1 sets drop to max(keep, drop + 1) and then adds 1 to keep. A 0 sets drop to keep and resets keep to 0. The deletion is required there, so the answer is the largest drop.

SWE Reasoning

Spot it

  • The question asks for the best sum of one unbroken run of an array.
  • You may delete at most one number from the run.
  • The deletion may be a number in the middle, which a plain subarray cannot skip.
  • Plain Kadane's Algorithm fails on a small example such as [1, -3, 1].
  • One value per position is not enough, because a run with a used deletion continues differently from a run without one.

The invariant, step by step

  1. Before the loop, keep and best are arr[0], and drop is minus infinity. No run with a deletion exists yet.
  2. For each x, drop = max(keep, drop + x) runs first. It reads the old keep, which does not include x.
  3. The first choice deletes x. The second choice adds x to a run that already deleted a number.
  4. keep = max(x, keep + x) is the Kadane step with nothing deleted.
  5. best = max(best, keep, drop) keeps the largest sum of either state.
  6. After the last number, best is the answer.

Traps

  • Wrong order. If keep changes first, drop copies a run that already holds x, and nothing is deleted. For [1, -3, 1], the result is 1 instead of 2.
  • Empty run after the deletion. Adding 0 to the max of drop allows an empty subarray. For [-1, -1, -1, -1], the result is 0 instead of -1.
  • Returning only keep. This is plain Kadane's Algorithm and never uses the deletion.
  • Starting drop at 0. At index 0, deleting the only number would leave an empty run. Start with minus infinity.
  • Treating the deletion as required. In this problem, the deletion is optional, so best takes keep too.

Practice

Canonical LeetCode:Maximum Subarray Sum with One Deletion (LC 1186)Longest Subarray of 1's After Deleting One Element (LC 1493)
© 2026 Hi👋WebEnterprise. All rights reserved.
Sitemap•llms.txt•