- 魔法师2026-10-13
力扣 LeetCode
3727. 最大交替平方和 - 力扣（LeetCode）
3727. 最大交替平方和 - 给你一个整数数组 nums。你可以以任意顺序 重新排列元素 。
数组 arr 的 交替得分 定义为：
* score = arr[0]2 - arr[1]2 + arr[2]2 - arr[3]2 + ...
在对 nums 重新排列后，返回其 最大可能的交替得分。
示例 1：
输入： nums = [1,2,3]
输出： 12
解释：
nums 的一种可行重排为...
思路
依旧贪心，(绝对值)贪心最大的一半加，最小的一半减。
代码```
class Solution {
public long maxAlternatingSum(int[] nums) {
long ans = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
nums[i] = nums[i] * nums[i];
}
Arrays.sort(nums);
int half = n >> 1;
for (int i = 0; i < half; i++) {
ans -= nums[i];
}
for (int i = half; i < n; i++) {
ans += nums[i];
}
return ans;
}
}主楼 - SomeBottle2026-10-13
按绝对值排序，然后按贪心思路分别取较大一端作为正项，较小一端作为负项来运算。```
class Solution {
public:
long long maxAlternatingSum(vector<int>& nums) {
// 按绝对值排序，正项从大的一端取，负项从小的一端取
sort(nums.begin(),nums.end(),[&](const int& a,const int& b){
return abs(a)<abs(b);
});
int l=0,r=nums.size()-1;
long long res=0;
while(l<=r){
// 先取大的
res+=(long long)nums[r]*nums[r];
r--;
if(l<=r){
// 负项取小的
res-=(long long)nums[l]*nums[l];
l++;
}
}
return res;
}
}; - tiansuohaoer2026-10-13
贪心，用nth_element求第k大可以做到O(n)```
class Solution {
public:
long long maxAlternatingSum(vector<int>& v) {
long long res=0,n=v.size();
for(auto &w:v){
w*=w;
res+=w;
}
nth_element(v.begin(),v.begin()+n/2,v.end());
return res-2ll*accumulate(v.begin(),v.begin()+n/2,0ll);
}
}; - Lvvvv2026-10-13
贪心```
class Solution {
public:
long long maxAlternatingSum(vector<int>& nums) {
sort(nums.begin(),nums.end(),[](const int& a, const int &b) -> bool {
return abs(a) < abs(b);
});
long long res = 0;
int n = nums.size();
for(int i = 0, j = n - 1; i <= j; i++,j--) {
res += nums[j] * nums[j];
if(i != j) res -= nums[i] * nums[i];
}
return res;
}
}; - GreenOnion2026-10-13
impl Solution { pub fn max_alternating_sum(mut nums: Vec<i32>) -> i64 { nums.sort_unstable_by_key(|&x| x.abs()); let n = nums.len(); nums[n/2..].iter().map(|&x| (x as i64).pow(2)).sum::<i64>() - nums[..n/2].iter().map(|&x| (x as i64).pow(2)).sum::<i64>() } } - Jerry20082026-10-13
#include <stdio.h> #include <stdlib.h> int sgn( int x ) { if ( x > 0 ) { return 1; } if ( x < 0 ) { return -1; } return 0; } int max( int x, int y) { if ( x < y ) { return y; } return x; } int compare_int(const void *a, const void *b) { return *(const int *)a - *(const int *)b; } long long maxAlternatingSum(int* nums, int numsSize) { long long nums_absl[ numsSize ]; for ( int i = 0 ; i < numsSize ; i++ ) { nums_absl[i] = sgn(nums[i])*nums[i]; } qsort(nums_absl, numsSize, sizeof(long long), compare_int); long long result = 0; for ( int i = 0; i < numsSize/2 ; i++ ) { result = result - (nums_absl[i]*nums_absl[i]); } for ( int i = numsSize / 2 ; i < numsSize ; i++ ) { result = result + (nums_absl[i]*nums_absl[i]); } return result; } ```好久没做了，复健复健 - CPython2026-10-13
class Solution: def maxAlternatingSum(self, nums: List[int]) -> int: n = len(nums) ans = 0 for i in range(n): nums[i] *= nums[i] nums.sort(reverse=True) if n & 1: for i in range((n >> 1) + 1): if i == (n >> 1): ans += nums[i] else: ans += nums[i] - nums[i+1+(n >> 1)] else: for i in range(n >> 1): ans += nums[i] - nums[i+(n >> 1)] return ans - 0wFF2026-10-14
impl Solution { pub fn max_alternating_sum(mut nums: Vec<i32>) -> i64 { let mut ans: i64 = 0; nums.sort_unstable_by_key(|&x| x.abs()); let len = nums.len(); let max = (len + 1) / 2; for (i, &x) in nums.iter().rev().enumerate() { if i < max { ans += (x as i64) * (x as i64); } else { ans -= (x as i64) * (x as i64); } } ans } }