力扣中國 · #3727

最大交替平方和(Maximum Alternating Sum of Squares)

對數組按絕對值降序排序,使用雙指針從兩端交替取值計算最大交替平方和。

開啟原題 ↗
時間複雜度O(n log n)
空間複雜度O(n)
解釋模型qwen/qwen3.8-27b

解題思路

作者很懶,所以我請 qwen/qwen3.8-27b 來幫他解釋。

將數組按絕對值從大到小排序,利用貪心策略:偶數位置取當前剩餘絕對值最大的數(平方後加),奇數位置取當前剩餘絕對值最小的數(平方後減),以最大化交替平方和。

通過的程式碼

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        nums = sorted(nums, key= lambda x: -1*abs(x))
        l = 0
        r = len(nums)-1
        ans = 0
        for i in range(len(nums)):
            if i %2 == 0:
                ans += nums[l]**2
                l+= 1
            else:
                ans -= nums[r]**2
                r-=1
        return ans