3727. Maximum Alternating Sum of Squares

1. Description

Reorder the integers in nums to maximize an alternating sum of their squares.
Starting at index 0, add the squared values at even indices and subtract those at odd indices: $nums[0]^2 - nums[1]^2 + nums[2]^2 - nums[3]^2 + \cdots$.
Return the largest score obtainable over all permutations.

2. Example

Example 1

Input: nums = [1,2,3]
Output: 12
Explanation: Arrange the elements as [2,1,3] to obtain $2^2 - 1^2 + 3^2 = 12$.

Example 2

Input: nums = [1,-1,2,-2,3,-3]
Output: 16
Explanation: The arrangement [-3,-1,-2,1,3,2] gives $(-3)^2 - (-1)^2 + (-2)^2 - 1^2 + 3^2 - 2^2 = 16$.

3. Constraints

• 1 <= nums.length <= $10^5$
• $-4 * 10^4$ <= nums[i] <= $4 * 10^4$

4. Solutions

Greedy with Sorting

n = nums.size()
Time complexity: O(n log n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// Assign the largest ceil(n / 2) squares to positive positions and the rest to negative positions.
class Solution {
public:
    long long maxAlternatingSum(vector<int> nums) {
        const int n = nums.size();

        sort(nums.begin(), nums.end(), [](long long a, long long b) { return a * a > b * b; });

        long long sum = 0;
        int pivot = n / 2 + n % 2;
        for (int i = 0; i < pivot; ++i) {
            sum += 1LL * nums[i] * nums[i];
        }

        for (int i = pivot; i < n; ++i) {
            sum -= 1LL * nums[i] * nums[i];
        }

        return sum;
    }
};