Best Run With One Skip

Medium1-D Dynamic Programming

Problem

Given an integer array nums, pick a contiguous run and then optionally remove at most one element from it. The run must still contain at least one element after the removal.

Return the largest possible sum of what remains.

Example 1

Input:
nums = [1, -2, 0, 3]
Output:
4

Take [1, -2, 0, 3] and drop -2.

Example 2

Input:
nums = [1, -2, -2, 3]
Output:
3

Dropping one -2 still leaves the other; [3] alone is best.

Example 3

Input:
nums = [-1, -1, -1, -1]
Output:
-1

You cannot drop the only element of a run.

Constraints

  • 1 ≤ nums.length ≤ 10^5
  • -10^4 ≤ nums[i] ≤ 10^4

Hint

Show the first hint

Extend the 'best run ending here' DP with a second state: whether you have already used your one removal.

Walkthrough

How to approach it

01Clarify before coding

  • Is removing optional? Yes, at most one.
  • Can the result be empty? No, at least one element must remain.
  • Must the removed element be inside the run? Yes; removing it splits nothing because the remaining parts are joined.

02Brute force

For every run and every choice of removed element (or none), compute the sum.

Cost: O(n³) naively, O(n²) with prefix sums and a running minimum: still too slow for 10^5.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.