Best Run With One Skip

Medium

You get an integer array values. Choose a contiguous segment of it and, if you like, throw out one of its elements. At least one element must remain afterwards. Return the largest sum you can get this way.

Example 1

values=[4, -5, 2, 6] → 12

Take the whole array and drop -5: 4 + 2 + 6 = 12.

Example 2

values=[-3, 7, -8, -8, 1] → 7

One skip cannot remove both -8s, so the best is just 7 on its own.

Example 3

values=[-4, -2, -6] → -2

The segment must not end up empty, so the answer is the single value -2.

Constraints

1 ≤ len(values) ≤ 10⁵
-10⁴ ≤ values[i] ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Fewest Jumps to the End Medium Most Profitable Streak Medium Reach the Last Cell Medium Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium

Input

values=[4, -5, 2, 6]

Expected

Run checks the first 3 tests in your browser. Submit checks all 142 tests on the server, hidden ones included.