跳转至

3727. 最大交替平方和

题目描述

给你一个整数数组 nums。你可以以任意顺序 重新排列元素 。

数组 arr 的 交替得分 定义为：

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

在对 nums 重新排列后，返回其 最大可能的交替得分。

 

示例 1：

输入： nums = [1,2,3]

输出： 12

解释：

nums 的一种可行重排为 [2,1,3]，该排列在所有可能重排中给出了最大交替得分。

交替得分计算如下：

score = 22 - 12 + 32 = 4 - 1 + 9 = 12

示例 2：

输入： nums = [1,-1,2,-2,3,-3]

输出： 16

解释：

nums 的一种可行重排为 [-3,-1,-2,1,3,2]，该排列在所有可能重排中给出了最大交替得分。

交替得分计算如下：

score = (-3)2 - (-1)2 + (-2)2 - (1)2 + (3)2 - (2)2 = 9 - 1 + 4 - 1 + 9 - 4 = 16

 

提示：

  • 1 <= nums.length <= 105
  • -4 * 104 <= nums[i] <= 4 * 104

解法

方法一：排序

我们可以将数组中的元素按其平方值进行排序，然后将平方值较大的元素放在偶数下标位置，平方值较小的元素放在奇数下标位置。

最终的交替得分即为平方值较大的元素之和减去平方值较小的元素之和，即数组 \(\text{nums}\) 排序后的后半部分元素平方和减去前半部分元素平方和。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(\log n)\)。其中 \(n\) 是数组的长度。

1
2
3
4
5
6
7
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public long maxAlternatingSum(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            nums[i] *= nums[i];
        }
        Arrays.sort(nums);
        long ans = 0;
        int m = n / 2;
        for (int i = 0; i < m; ++i) {
            ans -= nums[i];
        }
        for (int i = m; i < n; ++i) {
            ans += nums[i];
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    long long maxAlternatingSum(vector<int>& nums) {
        for (int& x : nums) {
            x = x * x;
        }
        ranges::sort(nums);
        long long ans = 0, m = nums.size() / 2;
        for (int i = 0; i < m; ++i) {
            ans -= nums[i];
        }
        for (int i = m; i < nums.size(); ++i) {
            ans += nums[i];
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func maxAlternatingSum(nums []int) (ans int64) {
    for i, x := range nums {
        nums[i] *= x
    }
    slices.Sort(nums)
    m := len(nums) / 2
    for _, x := range nums[:m] {
        ans -= int64(x)
    }
    for _, x := range nums[m:] {
        ans += int64(x)
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function maxAlternatingSum(nums: number[]): number {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        nums[i] = nums[i] ** 2;
    }
    nums.sort((a, b) => a - b);
    const m = Math.floor(n / 2);
    let ans = 0;
    for (let i = 0; i < m; i++) {
        ans -= nums[i];
    }
    for (let i = m; i < n; i++) {
        ans += nums[i];
    }
    return ans;
}

评论