3727.最大交替平方和：排序 (双指针可选)

【LetMeFly】3727.最大交替平方和：排序 (双指针可选)

力扣题目链接：https://leetcode.cn/problems/maximum-alternating-sum-of-squares/

给你一个整数数组 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

解题方法：排序

对数组以元素绝对值为依据排序，假设数组长度为$n$，加上$\lceil\frac{n}{2}\rceil$个最大元素的平方、减去$\lfloor\frac{n}{2}\rfloor$个最小元素的平方即为答案。

• 时间复杂度$O(n\log n)$，时间复杂度主要来自排序
• 空间复杂度$O(n)$，如果原地修改参数数组可以将空间复杂度降低到$O(\log n)$

AC代码

C++ —— 直接加前$\lceil\frac{n}{2}\rceil$个 然后减后 $\lfloor\frac{n}{2}\rfloor$ 个

/*
 * @LastEditTime: 2026-10-13 22:18:09
 */
typedef long long ll;
class Solution {
public:
    ll maxAlternatingSum(vector<int>& nums) {
        for (int& t : nums) {
            t = abs(t);
        }
        ranges::sort(nums, greater<int>());

        ll ans = 0;
        int half = (nums.size() + 1) / 2;
        for (int i = 0; i < half; i++) {
            ans = ans + nums[i] * nums[i];
        }
        for (int i = half; i < nums.size(); i++) {
            ans = ans - nums[i] * nums[i];
        }
        return ans;
    }
};

C++ —— 双指针，从两边开始一加一减

/*
 * @LastEditTime: 2026-10-13 22:15:35
 */
typedef long long ll;
class Solution {
public:
    ll maxAlternatingSum(vector<int>& nums) {
        for (int& t : nums) {
            t = abs(t);
        }
        ranges::sort(nums);

        ll ans = 0;
        for (int l = 0, r = nums.size() - 1; l <= r; l++, r--) {
            ans += (ll) (nums[r] * nums[r]);
            if (l == r) {
                break;
            }
            ans -= (ll) (nums[l] * nums[l]);
        }
        return ans;
    }
};

End

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源