The largest sum on a circle
A list of integers nums is arranged in a circle: the element after the last is the first. Return the
largest sum of a non-empty contiguous stretch, which may wrap around the end, but may use each element at most once.
Examples
| Input | Output | Why |
|---|---|---|
nums = [5,-3,5] | 10 | Wrap around: 5 + 5. |
nums = [1,-2,3,-2] | 3 | The 3 alone. |
nums = [-3,-2,-3] | -2 | All negative: the best single element, not the empty stretch. |
Constraints
- 1 ≤ nums.length ≤ 3 · 10⁴
- −3 · 10⁴ ≤ nums[i] ≤ 3 · 10⁴
Hints
Hint 1
A wrapping stretch leaves out a contiguous middle part.
Hint 2
The best wrapping stretch is the total minus the smallest-sum ordinary stretch.
Hint 3
If every number is negative, the "wrap" would be empty: return the ordinary maximum.
Where people lose marks
- Concatenating the list with itself and running Kadane, which can use an element twice.
- Returning 0 (an empty stretch) when all numbers are negative.
Dry run on [8,-1,-3,8]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 4nums80-11-3283best max8best min8total8
Run Kadane for the largest and the smallest stretch at once.
-
Step 2 / 4nums80-11-3283best max8best min-1total7
x = -1: largest stretch ending here 7, smallest -1.
-
Step 3 / 4nums80-11-3283best max8best min-4total4
x = -3: largest stretch ending here 4, smallest -4.
-
Step 4 / 4nums80-11-3283best max12best min-4total12
x = 8: largest stretch ending here 12, smallest 4. No wrap: 12. Wrap: total 12 − smallest -4 = 16. The answer is 16.
How to think about it
Either the best stretch does not wrap, and ordinary Kadane finds it, or it does wrap, and then the elements it leaves
out form an ordinary contiguous stretch in the middle. To maximise what remains, leave out the stretch with the smallest
sum: the wrapping answer is total − minimum subarray sum, found by Kadane with min instead of max. Take the
larger of the two, except when every element is negative: then the minimum stretch is the whole list and the "wrapping"
stretch would be empty, so return the ordinary maximum.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def max_circular(nums):
hi = lo = best_hi = best_lo = total = nums[0]
for x in nums[1:]:
hi = max(hi + x, x) # Kadane for the largest stretch
lo = min(lo + x, x) # and for the smallest
best_hi, best_lo = max(best_hi, hi), min(best_lo, lo)
total += x
if best_hi < 0:
return best_hi # all negative: no wrap possible
return max(best_hi, total - best_lo) # wrapping = total minus the left-out middle#include <algorithm>
#include <vector>
long long solve(const std::vector<int>& nums) {
long long hi = nums[0], lo = nums[0], bestHi = nums[0], bestLo = nums[0], total = nums[0];
for (size_t i = 1; i < nums.size(); ++i) {
long long x = nums[i];
hi = std::max(hi + x, x); lo = std::min(lo + x, x);
bestHi = std::max(bestHi, hi); bestLo = std::min(bestLo, lo);
total += x;
}
return bestHi < 0 ? bestHi : std::max(bestHi, total - bestLo);
}class Solution {
public long maxCircular(int[] nums) {
long hi = nums[0], lo = nums[0], bestHi = nums[0], bestLo = nums[0], total = nums[0];
for (int i = 1; i < nums.length; i++) {
long x = nums[i];
hi = Math.max(hi + x, x); lo = Math.min(lo + x, x);
bestHi = Math.max(bestHi, hi); bestLo = Math.min(bestLo, lo);
total += x;
}
return bestHi < 0 ? bestHi : Math.max(bestHi, total - bestLo);
}
}function maxCircular(nums) {
let hi = nums[0], lo = nums[0], bestHi = nums[0], bestLo = nums[0], total = nums[0];
for (let i = 1; i < nums.length; i++) {
const x = nums[i];
hi = Math.max(hi + x, x); lo = Math.min(lo + x, x);
bestHi = Math.max(bestHi, hi); bestLo = Math.min(bestLo, lo);
total += x;
}
return bestHi < 0 ? bestHi : Math.max(bestHi, total - bestLo); // wrap leaves out the worst middle
}fn solve(nums: &[i64]) -> i64 {
let (mut hi, mut lo, mut best_hi, mut best_lo, mut total) = (nums[0], nums[0], nums[0], nums[0], nums[0]);
for &x in &nums[1..] {
hi = (hi + x).max(x);
lo = (lo + x).min(x);
best_hi = best_hi.max(hi);
best_lo = best_lo.min(lo);
total += x;
}
if best_hi < 0 { best_hi } else { best_hi.max(total - best_lo) }
}solve :: [Int] -> Int
solve nums = if bestHi < 0 then bestHi else max bestHi (sum nums - bestLo)
where
kadane f = maximum . scanl1 (\end y -> f (end + y) y) -- best stretch ending at each position
bestHi = kadane max nums
bestLo = negate (kadane max (map negate nums))Variants to try
- Return the stretch's start and end on the circle.
- At most k elements long.
- Prefix sums and a monotonic deque over the doubled list give another O(n) solution.
Next problems
The largest-sum subarray
Return the largest sum of a non-empty contiguous subarray: the best sum ending at each position, extend or restart.
Open the problem → Easy10 minOne trade: the best profit
Buy on one day and sell on a later day. The best profit from selling today is today's price minus the lowest price so far.
Open the problem → Medium20 minThe largest product of a subarray
Return the largest product of a non-empty contiguous subarray. A negative number swaps the best and the worst, so keep both.
Open the problem →Write a solution and run it against the real test table.
Keep going
The largest-sum subarray
Return the largest sum of a non-empty contiguous subarray: the best sum ending at each position, extend or restart.
Open the problem → Easy10 minOne trade: the best profit
Buy on one day and sell on a later day. The best profit from selling today is today's price minus the lowest price so far.
Open the problem → Medium20 minThe largest product of a subarray
Return the largest product of a non-empty contiguous subarray. A negative number swaps the best and the worst, so keep both.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.