[LeetCode Python3] 396. Rotate Function + 暴力 + 错位相减

396. Rotate Function

暴力 时间复杂度O(n*n)

按照计算规则，一步一步来

class Solution:def maxRotateFunction(self, nums: List[int]) -> int:size, res = len(nums), -float('inf')for i in range(size):tmp = 0for j in range(size):tmp += j * nums[(j + size - i) % size]  # 用下标(j + size - i) % size来表示顺时针旋转i个位置res = max(res, tmp)return res

错位相减 时间复杂度O(2*n)

class Solution:def maxRotateFunction(self, nums: List[int]) -> int:size, nsum = len(nums), sum(nums)tmp = sum([i*nums[i] for i in range(size)])res = tmpfor i in range(1, size):tmp = tmp + nsum - size * nums[size-i]res = max(res, tmp)return res