Maximum Sum Circular Subarray

Medium#918best subarray

You get an array of whole numbers arranged in a ring: after the last number comes the first again. Pick a run of one or more neighbouring numbers, possibly going past the end and on from the start, but using each number at most once. Return its largest sum. Our example: [5, -2, -6, 3, -1, 4] — the answer is 11, the run [3, -1, 4, 5] that goes past the end.

918 Maximum Sum Circular SubarrayWalkthrough · 1×

Example: [5, -2, -6, 3, -1, 4]. The plain largest run is [3, -1, 4] = 6, but the answer is the run past the end: the whole ring, 3, minus its smallest run [-2, -6] = -8.

nums051-22-6334-154hiHerehiloHerelototal5
this stepthe run that hiHere sumsthe run that loHere sums; at the end, the part cut outread fromanswer: the run past the end

total = 5: the sum of the whole ring, so far only nums[0]

01/37
restart · back · play · step
Speed
1function maxCircular(nums):
2 total = nums[0]
3 hiHere = nums[0] // largest run that ends at i
4 hi = nums[0]
5 loHere = nums[0] // smallest run that ends at i
6 lo = nums[0]
7 for i from 1 to len(nums) - 1:
8 total = total + nums[i]
9 hiHere = max(nums[i], hiHere + nums[i])
10 hi = max(hi, hiHere)
11 loHere = min(nums[i], loHere + nums[i])
12 lo = min(lo, loHere)
13 if hi < 0:
14 return hi // every number is negative
15 return max(hi, total - lo)
state
i
–
total
5
hiHere
–
hi
–
loHere
–
lo
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The best run either stays inside the array, and plain Kadane finds it as hi, or it goes past the end. Then the numbers it leaves out form a run in the middle, and to make the kept part largest that left-out run must be the smallest: total - lo.
  2. The smallest run is found the same way as the largest, with min instead of max, in the same pass.
  3. If every number is negative, the smallest run is the whole ring and total - lo = 0 stands for taking nothing, which is not allowed. Then hi, the largest single number, is returned instead.

Complexity

Time O(n): one pass, each number updates five values. Memory O(1): five numbers; the rows in the picture show their history.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.