Maximum Sum of Consecutive Differences (Circular)

Maximum Sum of Consecutive Differences (Circular) looks like a hard arrangement problem — try every circular ordering and the search space explodes. But a single sort plus one clean observation collapses it to an O(n log n) formula. It is a classic greedy insight.

The slow way first

The brute-force approach tries every circular permutation of the array and scores each one. With n! orderings, this is hopeless past tiny inputs. Even pruning is messy because the circle has no fixed start.

The question to ask: which numbers should sit next to which? Big jumps come from putting small numbers next to large numbers. So we want to alternate lows and highs as much as possible — never waste an edge between two values that are close together.

The idea: sort, then split into halves

Sort the array. Call the smaller n/2 values the lower half and the larger n/2 values the upper half. In the best circle, every large value sits between two small values and every small value sits between two large values. When you expand all the absolute differences, each upper-half value is added twice and each lower-half value is subtracted twice.

So the answer is simply 2 * (sum of upper half − sum of lower half).

The key insight: you never need to construct the actual arrangement. The sorted split tells you exactly which numbers play the role of peaks and which play the role of valleys.

Walk through it

Step through the animation. We start with [4, 2, 1, 8], sort it to [1, 2, 4, 8], then highlight the two halves. The lower half 1, 2 sums to 3; the upper half 4, 8 sums to 12. The answer is 2 × (12 − 3) = 18 — matching the hand-built circle above.

Pseudocode

sort nums ascending
half = n / 2
lower = sum of the first half of nums      # the smallest values
upper = sum of the second half of nums     # the largest values
return 2 * (upper - lower)

The Python solution

def max_circular_diff(nums):
    n = len(nums)
    nums.sort()
    half = n // 2
    lower = 0
    for x in nums[:half]:
        lower += x
    upper = 0
    for x in nums[half:]:
        upper += x
    return 2 * (upper - lower)

• nums.sort() is the whole trick — once sorted, the smallest and largest values are cleanly separated.
• half = n // 2 splits the sorted array down the middle.
• The first loop sums the lower half (nums[:half]), the values that will act as valleys.
• The second loop sums the upper half (nums[half:]), the values that will act as peaks.
• 2 * (upper - lower) is the closed-form answer: each peak contributes +2, each valley −2.

Complexity

The sort dominates the runtime; the two summation passes are linear. Beyond the sort we use only a couple of accumulators, so the extra space is O(1).

When this pattern shows up

Practice