跳转至

3727. 最大交替平方和

来源第 473 场周赛 Q2难度中等分数1454

题目描述

给你一个整数数组 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
8
class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        nums = [x * x for x in nums]
        nums.sort()
        ans, m = 0, len(nums) >> 1
        for i, x in enumerate(nums):
            ans += -x if i < m else x
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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 >> 1;
        for (int i = 0; i < n; ++i) {
            ans += i < m ? -nums[i] : nums[i];
        }
        return ans;
    }
}

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function maxAlternatingSum(nums: number[]): number {
    nums = nums.map(x => x * x).sort((a, b) => a - b);
    let ans = 0;
    const n = nums.length;
    const m = n >> 1;
    for (let i = 0; i < n; i++) {
        ans += i < m ? -nums[i] : nums[i];
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
impl Solution {
    pub fn max_alternating_sum(nums: Vec<i32>) -> i64 {
        let mut nums: Vec<i64> = nums
            .into_iter()
            .map(|x| i64::from(x) * i64::from(x))
            .collect();
        nums.sort();
        let m = nums.len() >> 1;
        let mut ans = 0i64;
        for (i, &x) in nums.iter().enumerate() {
            ans += if i < m { -x } else { x };
        }
        ans
    }
}

评论