0275MediumArrayDivide and ConquerDynamic ProgrammingQueueMonotonic Queue

Best Arc of the Ring Road

Tracked in this browser only

Trains the technique from

LeetCode 918Maximum Sum Circular Subarray

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A ring road is split into n tolled sections laid end to end around a circle and numbered 0 through n - 1, with section n - 1 running straight into section 0. ledger[i] is last quarter's net result for section i, in thousands, and it is negative on a section whose upkeep cost more than its tolls brought in.

An arc is a non-empty run of sections taken in ring order, so an arc is allowed to carry on past section n - 1 and continue at section 0. An arc may not visit a section twice, so it holds between 1 and n sections.

Return the largest net total any single arc reaches.

Examples

Example 1

Input: ledger = [5, -3, 6, -9, 4]
Output: 12

The arc that begins at section 4 and carries on through sections 0, 1 and 2 totals 4 + 5 - 3 + 6 = 12.

Example 2

Input: ledger = [3, -1, 3]
Output: 6

The arc holding section 2 and then section 0 totals 3 + 3 = 6.

Example 3

Input: ledger = [-4, -2, -7]
Output: -2

Section 1 on its own is an arc, and its total is -2.

Constraints

n == ledger.length
1 <= n <= 3 * 10^4
-3 * 10^4 <= ledger[i] <= 3 * 10^4

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def best_ring_arc(ledger: list[int]) -> int:

Java

public int bestRingArc(int[] ledger)

The intended approach

Time O(n)Space O(1)

An arc either stays inside the array as written or wraps, and a wrapping arc is precisely the whole ring with one inner run of sections removed. So one pass keeps four running figures: the best run ending at the current section and the best seen so far, and the same two for the worst run. The answer is the larger of the best plain run and the whole-ring total minus the worst run, except that the removed run must itself be non-empty, so a ring where every section loses money reports the best plain run instead.

Pythonentry point: best_ring_arc

def best_ring_arc(ledger):
    # One pass carrying two running figures side by side: the best run of
    # consecutive sections ending here, and the worst such run.  A wrapping arc is
    # the whole ring with one inner run cut out, so the whole-ring total minus the
    # worst run is the best wrapping arc.  That cut-out run has to be non-empty,
    # which is why an all-negative ring falls back on the best plain run.
    # Time: O(n), single pass, no slicing.  Space: O(1), five scalars.
    total = ledger[0]
    best = cur_best = ledger[0]
    worst = cur_worst = ledger[0]
    for i in range(1, len(ledger)):
        v = ledger[i]
        total += v
        cur_best = v if cur_best < 0 else cur_best + v
        if cur_best > best:
            best = cur_best
        cur_worst = v if cur_worst > 0 else cur_worst + v
        if cur_worst < worst:
            worst = cur_worst
    if best < 0:
        return best
    wrapped = total - worst
    return wrapped if wrapped > best else best

The obvious version

Take every starting section and every arc length from 1 to n, add the sections up one at a time with wraparound indexing, and keep the largest total seen.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_best_ring_arc(ledger):
    n = len(ledger)
    best = None
    for start in range(n):
        running = 0
        for length in range(1, n + 1):
            running += ledger[(start + length - 1) % n]
            if best is None or running > best:
                best = running
    return best

How this problem was checked

Reference solution executed against 9 test cases — 9 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in