You are given an integer array nums, and you are allowed to rearrange its elements in any order you like.

The alternating score of an array arr is calculated by squaring each element and then alternating between adding and subtracting these squares, starting with addition:

• score = arr[0]² - arr[1]² + arr[2]² - arr[3]² + ...

In other words:

• Elements at even indices (0, 2, 4, ...) have their squares added to the score.
• Elements at odd indices (1, 3, 5, ...) have their squares subtracted from the score.

Your task is to rearrange the elements of nums so that this alternating score is as large as possible, and return that maximum possible alternating score.

For example, if nums = [3, -1, 2, 4], one optimal arrangement is [4, -1, 3, 2], giving a score of 4² - (-1)² + 3² - 2² = 16 - 1 + 9 - 4 = 20.

Key observations about the problem:

1. Since every element is squared, the sign of the original number does not matter — only the magnitude of its square does.
2. Rearranging freely means you get to choose which elements are added and which are subtracted. With n elements, ⌈n / 2⌉ of them land on even indices (added) and ⌊n / 2⌋ land on odd indices (subtracted).
3. To maximize the score, you want the elements with the largest squares to be added and the elements with the smallest squares to be subtracted.

This leads directly to a sorting strategy: sort the array by squared value, subtract the sum of squares of the smaller half (nums[: n // 2]), and add the sum of squares of the larger half (nums[n // 2 :]). The answer is s2 - s1, where s2 is the sum of squares of the larger half and s1 is the sum of squares of the smaller half.

The first thing to notice is that the score formula only ever uses squared values. Once we square an element, its original sign disappears — (-3)² and 3² are both 9. So the problem really boils down to working with the squares of the numbers, not the numbers themselves.

The second key insight comes from the freedom to rearrange. The alternating pattern + - + - ... looks complicated at first, but since we can place elements anywhere, the positions themselves stop mattering. All that matters is a simple partition:

• Some elements end up at even indices, and their squares are added.
• The rest end up at odd indices, and their squares are subtracted.

So the question transforms into: which elements should be added, and which should be subtracted?

With n elements, exactly ⌈n / 2⌉ slots are "plus" slots and ⌊n / 2⌋ are "minus" slots. To maximize (sum of added squares) - (sum of subtracted squares), a greedy choice is obvious:

• Put the elements with the largest squares into the plus slots.
• Put the elements with the smallest squares into the minus slots.

Swapping any large-square element out of a plus slot for a smaller one can only decrease the total, so this greedy assignment is optimal.

This naturally suggests sorting by squared value. After sorting:

• The first half nums[: n // 2] holds the smallest squares — these get subtracted (s1).
• The second half nums[n // 2 :] holds the largest squares — these get added (s2). Note that when n is odd, this half is one element bigger, which correctly matches the extra plus slot at index 0.

The answer is simply s2 - s1.

Pattern Learn more about Greedy and Sorting patterns.

The implementation follows directly from the greedy insight: sort by squared value, subtract the small half, add the large half. Let's walk through the code step by step.

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        nums.sort(key=lambda x: x * x)
        n = len(nums)
        s1 = sum(x * x for x in nums[: n // 2])
        s2 = sum(x * x for x in nums[n // 2 :])
        return s2 - s1

Step 1: Sort by squared value

nums.sort(key=lambda x: x * x)

We sort using the key x * x rather than x itself. This is important because the array may contain negative numbers — sorting by raw value would place -5 before 2, but in terms of squares, (-5)² = 25 is larger than 2² = 4. Sorting by x * x guarantees the elements are ordered by their actual contribution to the score, from smallest square to largest square.

Step 2: Split the array into two halves

With n = len(nums), the sorted array is divided at index n // 2:

• nums[: n // 2] — the ⌊n / 2⌋ elements with the smallest squares. These are conceptually placed at odd indices, so their squares form the subtracted sum s1.
• nums[n // 2 :] — the ⌈n / 2⌉ elements with the largest squares. These go to even indices, and their squares form the added sum s2.

The split point n // 2 handles both parities of n correctly:

• If n is even, both halves have exactly n / 2 elements, matching the equal number of plus and minus slots.
• If n is odd, the second half gets one extra element — matching the fact that even indices (0, 2, 4, ...) outnumber odd indices by one.

Step 3: Compute the two sums and return the difference

s1 = sum(x * x for x in nums[: n // 2])
s2 = sum(x * x for x in nums[n // 2 :])
return s2 - s1

Each generator expression squares the elements of its half and sums them up. The maximum alternating score is then simply s2 - s1.

Walkthrough with an example

Take nums = [3, -1, 2, 4]:

1. Sorting by square: [-1, 2, 3, 4] (squares: 1, 4, 9, 16).
2. n = 4, split point is 2:
   • First half [-1, 2] → s1 = 1 + 4 = 5
   • Second half [3, 4] → s2 = 9 + 16 = 25
3. Answer: s2 - s1 = 25 - 5 = 20.

This corresponds to the arrangement [4, -1, 3, 2] (or [3, 2, 4, -1], etc. — any arrangement where 3 and 4 occupy even indices).

Complexity Analysis

• Time complexity: O(n log n), dominated by the sort. The two summation passes are O(n) each.
• Space complexity: O(log n) for the sorting routine's internal stack (or O(n) if counting the temporary slices nums[: n // 2] and nums[n // 2 :]; this can be reduced to O(1) extra space by summing with index ranges instead of slicing).

Alternative implementations

• Single-pass after sorting: Instead of slicing, iterate once and add x * x when the index is ≥ n // 2, subtract otherwise — avoiding the extra slice copies.
• Quickselect: Since we only need to partition the squares around the median rather than fully sort them, a quickselect-based approach could achieve O(n) average time. For typical input sizes, however, the simplicity of sorting is usually preferable.