每日leetcode-数组-396. 旋转函数

分类：数组-数组的旋转

题目描述：

给定一个长度为 n 的整数数组 A 。

假设 Bk 是数组 A 顺时针旋转 k 个位置后的数组，我们定义 A 的“旋转函数” F 为：

F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]。

计算F(0), F(1), ..., F(n-1)中的最大值。

注意:
可以认为 n 的值小于 105。

解题思路：

重点是找到F（x）之间的数量关系。

可以发现除了最后一项以外，其余项都比上一项前面的系数多一；用前一个F 减去最后一项与权重的积:(n-1)*nums[n-1]
再加上剩下每一项乘1:sum(nums)-num[n-1] 得到新的F

F(n)=F(n-1)+sum-n*nums[pos];

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        if len(nums) <=1:
            return 0
        all_sum = sum(nums)
        maxf =f = sum(i*nums[i] for i in range(len(nums)))
        for i in range(1,len(nums)):
            f = f + all_sum - len(nums)*nums[-i]
            maxf = max(maxf,f)
        return maxf