Maximize the Difference 2
Time limit1sMemory limit512 MB
Given N integers, permute them to maximize the sum of absolute differences of adjacent elements and print the maximum.
- Level
Medium7 of 10
- Topics
- Sorting, Greedy, Math, Implementation
- Solved
- No attempts yet
Problem
An array A of N integers is given. Rearrange the order of the integers in the array as you like and write a program that finds the maximum value of the following expression.
|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|
Input
The first line gives N (3 ≤ N ≤ 1,000,000). The second line gives the integers in array A. Each integer in the array is greater than or equal to -100,000 and less than or equal to 100,000.
Output
On the first line, print the maximum value of the expression obtainable by rearranging the order of the numbers in the array.