Show problems as
Classic problem #918MediumArrayDivide and ConquerDynamic ProgrammingQueueMonotonic Queue

Maximum Sum Circular Subarray

Real-world version: Best Arc of the Ring Road
Tracked in this browser only
Read Maximum Sum Circular Subarray on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_ring_arc(ledger: list[int]) -> int:
Java
public int bestRingArc(int[] ledger)

More on the same topics