Around the corner
The best run in a circle is either an ordinary run, or everything except the worst run. About 10 minutes.
When the end joins the start
A food stall is open every day, all year round, and you want its best run of consecutive days, where the run may wrap from December into January. In an array arranged in a circle, the last box sits next to the first.
So a run is one of two kinds. Either it's an ordinary run inside the array, which Kadane's walk already finds. Or it wraps round: a piece at the end plus a piece at the start.
- best
- 7
- total
- 7
Ordinary runs first. Kadane's gives the best one: 5 - 3 + 5 = 7.
A wrapping run skips the worst middle
A wrapping run uses everything except one stretch in the middle. To make it as big as possible, skip the stretch with the smallest total. So the best wrapping run is the total of everything minus the worst stretch, from the last step.
The answer is the bigger of the two kinds. One catch: if every number is negative, "skip the worst stretch" means skipping everything, which isn't allowed. Then just use the ordinary best.
# the walks from the last two steps:
best = kadane_max(nums)
if best < 0:
return best
worst = kadane_min(nums)
return max(best, sum(nums) - worst)In a circle of 2, −10, 3: the total is −5, the best ordinary run is 3, and the worst stretch is −10. What's the answer?
- A5
- B3
- C−5
Show the answer
5. −5 − (−10) = 5: the run 3, 2 wraps round the end.
Best run in a circle
You get a non-empty list of numbers arranged in a circle, so the last number is followed by the first. Return the largest sum of a non-empty run of consecutive numbers, where a run may wrap around but may not use any number twice.
nums = [5, -3, 5] → 10
1 ≤ n ≤ 1,000,000 · −10^6 ≤ each value ≤ 10^6 · return a long