第 473 场周赛Q2——3727. 最大交替平方和

题目链接：3727. 最大交替平方和（中等）

算法原理：

解法：贪心

133ms击败11.31%

时间复杂度O(Nlogn)

想要最大可能的交替得分最大，那就要让绝对值大的前面放+，绝对值小的前面放-，那就先按绝对值大小排序，在后半个数组前面放+，在前半个数组前面放-

Java代码：

class Solution { public long maxAlternatingSum(int[] arr) { Integer[] nums=new Integer[arr.length]; for(int i=0;i<arr.length;i++) nums[i]=(Integer)arr[i]; //按绝对值，从小到大排序 Arrays.sort(nums,(a,b)->Math.abs(a)-Math.abs(b)); int n=nums.length; int mid=n/2; int[] mi=new int[n]; int[] ma=new int[n]; for(int i=0;i<mid;i++) mi[i]=-1*nums[i]*nums[i]; for(int i=mid;i<n;i++) ma[i]=nums[i]*nums[i]; long ret=0; for(int i=0;i<n;i++) ret+=(long)ma[i]+(long)mi[i]; return ret; } }