October 13Medium

Maximum alternating sum of squares

Array
Greedy
Sorting

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.

Solution

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        nums.sort(key=lambda x: abs(x))
        n = len(nums)
        res = 0 if not n % 2 else nums[n//2] ** 2
        for i in range(n // 2):
            res += nums[n - 1 - i] ** 2 - nums[i] ** 2

        return res