367. Maximum Sum of Absolute Difference of an Array

Given an array of n integers, rearrange its elements in a straight line (not circular) to maximize the sum of |arr[i] - arr[i+1]| over all consecutive pairs i = 0..n-2. Print that maximum possible sum (print 0 if n = 1).

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 differences of consecutive elements after rearranging (0 if n = 1).

1 <= n <= 10^5

This is the LINEAR (non-circular) sibling of 'Maximize Sum of Consecutive Differences in a Circular Array' - the circular version has a cleaner, more symmetric structure (every element touches exactly two neighbors), while this linear version needs special handling for the two endpoints that only touch one neighbor each.

Rearrange an array in a straight line to maximize the sum of absolute differences between consecutive elements. Brute force: Try every possible permutation of the array and compute the sum of consecutive absolute differences for each - this is factorial time, only feasible for very small n, though useful for verifying the correct pattern by hand. Optimised: Alternating between low-half and high-half values (in a zigzag pattern) ensures nearly every consecutive pair crosses the low-high boundary, maximizing each individual difference - this constructive pattern, once identified, directly builds the optimal arrangement without needing to search through permutations.

Generate every possible permutation (ordering) of the array's elements, and for each one compute the sum of |arr[i] - arr[i+1]| over all consecutive pairs, keeping track of the maximum sum found across all arrangements. This exhaustively checks every possible ordering and is guaranteed to find the true maximum, but the number of permutations grows factorially, making this completely impractical beyond very small arrays. Time: O(n! * n) Space: O(n)

Sort the array first, then construct a specific 'wave-like' arrangement by alternately placing elements from the low end and the high end of the sorted array (using two pointers moving toward the middle), which places small and large values next to each other to maximize the absolute differences between neighbors. Then compute the sum of consecutive absolute differences directly from this constructed arrangement. Sorting first and using this alternating construction produces a provably optimal or near-optimal arrangement in far less time than trying every permutation, though it does require actually building the rearranged array and then a separate pass to sum its differences. Time: O(n log n) Space: O(n)

Sort the array, and observe that in an optimal wave arrangement, each element's total contribution to the final sum depends only on how many times it ends up acting as a 'peak' (added) versus a 'valley' (subtracted) - a pattern that depends solely on its rank in the sorted order, not on physically constructing the arrangement. By summing up the top half of sorted values with a positive weight and the bottom half with a negative weight according to this fixed pattern, the maximum sum can be computed directly from the sorted array in one pass, without ever constructing an actual rearranged array or computing consecutive differences explicitly, saving the extra array-construction and difference-summing passes that the better approach needs. Time: O(n log n) Space: O(1) extra, beyond the sort

1. Recognize that end positions touch only ONE neighbor, while interior positions touch TWO - so it pays to let the most EXTREME (very high or very low) values do double duty in the interior. 2. Sort the array, then split it into a 'low half' and 'high half'. 3. Arrange the values alternating between low and high groups through the interior, with the most extreme values placed carefully at the boundaries - reasoning through small cases by hand (or a known constructive pattern) reveals the exact optimal arrangement.

Time: O(n log n), dominated by sorting the array before constructing the zigzag arrangement. Space: O(n), for the rearranged output array.

n = 1 (print 0, per the problem statement), n = 2, and n at its maximum of 10^5 to confirm the rearrangement strategy runs efficiently.

Be ready to work through a small example by hand to justify the low/high alternating pattern, since the exact optimal construction can be non-obvious without concrete small-case experimentation first.