What is the brute force approach and complexity for Maximum Subarray Sum with One Deletion?

Try deleting each element (or none), run Kadane on the rest, keep the best with time complexity O(N^2) and space complexity O(1).

What is the optimal approach and complexity for Maximum Subarray Sum with One Deletion?

One pass with keep (no deletion yet) and del (one deleted); update both with optimal time complexity O(N) and space complexity O(1).

Maximum Subarray Sum with One Deletion

Q: How do you identify the pattern for Maximum Subarray Sum with One Deletion?

Look for key signals in the prompt: "delete at most one element" indicates Two states per index: no deletion yet, or the one deletion already used.; "contiguous subarray" indicates A run can cross the gap left by the deleted element, so it can join two runs that were apart.; "must keep at least one element" indicates The answer comes from a non-empty run. When every number is negative, the answer is the largest single number..

Medium·LeetCode #1186 Pro OnlyMedium

LeetCode

Problem Statement

You are given an integer array arr. You may delete at most one element. When an element is deleted, its two neighbours touch, so a run can now cross the gap.

After the optional deletion, find a non-empty contiguous subarray with the largest sum, and return that sum. You must keep at least one element, so a result with nothing left is not allowed.

Input

An integer array arr of length n.

Output

One number: the largest sum of a non-empty subarray, after deleting at most one element.

Example 1

Input: arr = [1, -2, 0, 3]

Output: 4

Delete the -2. The array becomes [1, 0, 3], which sums to 4.

Example 2

Input: arr = [1, -2, -2, 3]

Output: 3

Without a deletion, the best run is [3] = 3. Deleting one -2 leaves [1, -2, 3], whose best run is still 3, so deleting does not help.

Example 3

Input: arr = [-1, -1, -1, -1]

Output: -1

Deleting is allowed, but one element must stay. The best choice is a single -1.

Constraints

• 1 ≤ arr.length ≤ 10^5
• −10^4 ≤ arr[i] ≤ 10^4

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“delete at most one element”

→ Two states per index: no deletion yet, or the one deletion already used.

“contiguous subarray”

→ A run can cross the gap left by the deleted element, so it can join two runs that were apart.

“must keep at least one element”

→ The answer comes from a non-empty run. When every number is negative, the answer is the largest single number.

Approach Complexity Ladder

Brute Force — try every deletionO(N^2)O(1)

Try deleting each element (or none), run Kadane on the rest, keep the best

Better — best run on each side of the gapO(N)O(N)

Precompute left[i] (run ending at i) and right[i] (run starting at i); answer = left[i−1] + right[i+1]

Optimal — two running valuesO(N)O(1)

One pass with keep (no deletion yet) and del (one deleted); update both

Brute Force Intuition

There are only n + 1 choices: delete nothing, or delete element d for each d. For each choice, run Maximum subarray on what is left, and keep the largest answer.

Recognition rule for this sub-pattern:

cur = max(x, cur + x); best = max(best, cur).

Remember this · DP — Kadane / Subarray

Trigger

Maximum (or minimum) sum/product of a contiguous subarray, stock buy/sell, circular arrays.

Think

Is the best subarray ending at i either "i alone" or "best ending at i−1, plus i"?

Key question

Should I extend or restart?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Kadane / Subarray translate into production architectures and low-level memory mechanics.

LLD Architecture