368. Maximize Sum of Consecutive Differences in a Circular Array

Given an array of n integers, rearrange its elements around a circle to maximize the sum of |arr[i] - arr[(i+1) mod n]| over all n consecutive pairs, including the wraparound pair. Print that maximum possible sum.

Input: The first line contains an integer n. The second line contains n space-separated integers, the array elements. Output: Print a single integer - the maximum possible sum of absolute consecutive differences arranged around a circle.

1 <= n <= 10^5

The CIRCULAR symmetry here (every position has exactly 2 neighbors) is what makes this problem have a clean closed-form answer, unlike its linear counterpart 'Maximum Sum of Absolute Difference of an Array', which needs special-case handling for its two single-neighbor endpoints.

Rearrange an array in a circle to maximize the sum of absolute differences between every pair of neighbors, including the wraparound pair. Brute force: Try every possible circular arrangement and compute the sum of consecutive differences for each - this is factorial time, impractical for large n, when the elegant sorted-split formula gives the answer directly. Optimised: Because the circle is symmetric (every element touches exactly two neighbors, unlike a linear arrangement's endpoints), splitting into a lower and upper half and alternating between them makes EVERY single edge cross the low-high boundary - and the clean mathematical identity (2 * (upper sum - lower sum)) computes the total directly without ever needing to construct the actual arrangement.

Sort the array, then build one concrete arrangement by alternating between placing the next-largest and next-smallest remaining elements around the circle, and directly compute the sum of adjacent absolute differences for that single constructed arrangement. This uses the insight that maximizing differences means keeping big and small values adjacent, avoiding the need to explore every permutation, but it still requires building and walking through the full arrangement to total the differences. Time: O(n log n) Space: O(n)

Sort the array and observe that in the optimal arrangement, each element ends up acting as either a local high point or a local low point relative to its two neighbors; working out how many times each element contributes positively versus negatively shows that the answer equals 2 * (sum of the largest n/2 elements - sum of the smallest n/2 elements). This closed-form total is computed directly from the sorted array in one pass, without ever constructing or simulating the actual circular arrangement. Time: O(n log n) Space: O(1)

Generate every possible circular arrangement (permutation) of the n elements, and for each one compute the sum of |arr[i] - arr[(i+1) mod n]| over all n adjacent pairs including the wraparound pair, keeping track of the largest total seen across all arrangements. This is guaranteed correct since it literally tries every arrangement, but the number of permutations grows factorially with n. Time: O(n! * n) Space: O(n)

1. Sort the array and split it into a 'lower half' and an 'upper half' of equal (or near-equal) size. 2. Arrange the circle so it alternates between the lower half and the upper half - this makes EVERY edge cross between a small and a large value, maximizing each individual difference. 3. The resulting maximum sum equals exactly TWICE the difference between the sum of the upper half and the sum of the lower half.

Time: O(n log n), dominated by sorting the array to find the lower/upper split. Space: O(1) extra space beyond the sort itself, since the final answer is computed via a direct formula.

n = 1 or n = 2, duplicate values in the array, and n at its maximum of 10^5 to confirm the sort-and-split approach runs efficiently.

Be ready to derive WHY the answer is exactly 2*(upper sum - lower sum) - each upper-half value contributes positively twice (once for each of its two neighbor-edges) and each lower-half value contributes negatively twice, in a perfectly alternating arrangement.