1. 题意
给你一个整数数组 nums。你可以以任意顺序 重新排列元素 。
数组 arr 的 交替得分 定义为：
s c o r e = a r r [ 0 ] 2 − a r r [ 1 ] 2 + a r r [ 2 ] 2 − a r r [ 3 ] 2 + . . . score = arr[0]^2 - arr[1]^2 + arr[2]^2 - arr[3]^2 + ...score=arr[0]2−arr[1]2+arr[2]2−arr[3]2+...
在对 nums 重新排列后，返回其 最大可能的交替得分。
2. 题解
真的是没有系统的思考过，但是还是做出来了。
大致作法是按绝对值进行排序，绝对值小的当作负数项就好了。
实际上看了题解后，感觉自己太死板了。
其实这个题目就是求
max { s ∣ s = ∑ i = 0 n − 1 ( − 1 ) i a i 2 } \max \{ s |s=\sum_{i=0}^{n-1} (-1)^{i}a_i^2\}max{s∣s=i=0∑n−1(−1)iai2}
我们可以拆成两个部分
s = ∑ i = 0 ⌈ n / 2 ⌉ x i 2 − ∑ i = 0 ⌊ n / 2 ⌋ y i 2 s=\sum_{i=0}^{ \lceil n / 2\rceil}x_i^2 - \sum_{i=0}^{\lfloor n/2\rfloor}y_i^2s=i=0∑⌈n/2⌉xi2−i=0∑⌊n/2⌋yi2
其中x i y i ∈ a r r x_i y_i \in arrxiyi∈arr
因此我们只需要前面的项尽可能大，后面的项尽可能小就可以使得最终值最大。
最终的代码就不太重要了。
还有一个小细节就是，我们可以先把每个值都先变为平方再去排序；
也可以先按绝对值排序再平方处理。
前一种方法在处理上理简便一些。
2.1 my solution
classSolution{public:staticboolcmp(inta,intb){returnstd::abs(a)<std::abs(b);}longlongmaxAlternatingSum(vector<int>&nums){// 1 2 3 4// 2 1 4 3 = 3 + 7 = 10// 4 1 3 2 = 15 + 5 = 20// 4 2 3 1 = 12 + 8 = 20// -3 -2 -1 1 2 3// 1 1 2 2 3 3// 3 1 3 1 2 2 = 8 + 8 = 16sort(nums.begin(),nums.end(),cmp);intn=static_cast<int>(nums.size());intoff=n/2;longlongans=0;for(inti=0;i<off;++i){ans+=1LL*nums[i+off]*nums[i+off]-nums[i]*nums[i];}if(1==n%2)ans+=nums[n-1]*nums[n-1];returnans;}};2.2 官解
classSolution{public:longlongmaxAlternatingSum(vector<int>&nums){intn=nums.size();for(auto&num:nums){num*=num;}ranges::sort(nums);return-accumulate(nums.begin(),nums.begin()+n/2,0LL)+accumulate(nums.begin()+n/2,nums.end(),0LL);}};参考
leetcode
