Circular Track Best Segment

Medium1-D Dynamic Programming

Problem

A running track is split into n sections in a loop; gains[i] is the energy you gain (or lose, if negative) on section i. Section n - 1 is followed by section 0.

Choose a segment: one or more consecutive sections around the loop, each used at most once. Return the largest total gain of any segment.

Example 1

Input:
gains = [5, -3, 5]
Output:
10

The segment wraps: sections 2 and 0, 5 + 5.

Example 2

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

Section 2 alone.

Example 3

Input:
gains = [-3, -2, -3]
Output:
-2

Everything is negative, so take the single best section.

Constraints

  • 1 ≤ gains.length ≤ 3·10^4
  • -3·10^4 ≤ gains[i] ≤ 3·10^4

Hint

Show the first hint

A segment either stays inside the array or wraps around the end. Handle the non-wrapping case with the best-streak DP.

Walkthrough

How to approach it

01Clarify before coding

  • Can the segment be the whole loop? Yes, as long as each section is used once.
  • Non-empty? Yes, so all-negative input returns the largest element.
  • Can it wrap more than once? No, each section at most once.

02Brute force

For every start section, walk up to n sections around the loop summing as you go.

Cost: O(n²) time: about 9·10^8 steps for n = 3·10^4.

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.