力扣中國 · #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