Loading problem…
You are given an integer array nums. You may rearrange the elements in any order. The alternating score of an array arr is defined as: score = arr[0]^2 - arr[1]^2 + arr[2]^2 - arr[3]^2 + ... Return an integer denoting the maximum possible alternating score of nums after rearranging its elements.
Example 1
Input: nums = [1,2,3]
Output: 12
Explanation: The squares are 1, 4 and 9. With three elements there are two adding slots and one subtracting slot, so add the two largest and subtract the smallest: 9 + 4 - 1 = 12.
Example 2
Input: nums = [1,-1,2,-2,3,-3]
Output: 16
Explanation: Signs don't matter because every value is squared, giving squares 1, 1, 4, 4, 9, 9. Six elements means three adding slots and three subtracting slots: (9 + 9 + 4) - (4 + 1 + 1) = 16.
Example 3
Input: nums = [5]
Output: 25
Explanation: A single element fills the only adding slot and there is nothing to subtract, so the score is just 5 squared, which is 25.
Every term is squared, so signs don't matter and the problem is really about a multiset of squared values. The number of adding slots (even indices) and subtracting slots (odd indices) is fixed by the length, so to maximise the score you greedily send the largest squares to the plus slots and the smallest to the minus slots. Sorting descending and adding the first ceil(n/2) values, subtracting the rest, does exactly that.
Run checks all cases above. Submit evaluates all test cases.