Leetcode每日一题 —— 3727. 最大交替平方和

按绝对值排序，然后按贪心思路分别取较大一端作为正项，较小一端作为负项来运算。

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;

    }

};

贪心，用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);

    }

};

贪心

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;

    }

};

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>()

    }

}

#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;

}

好久没做了，复健复健

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

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

    }

}

uwu