题目

Given an array of integers A and let n to be its length.

Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a "rotation function" F on A as follow:

Calculate the maximum value of F(0), F(1), ..., F(n-1).

思路

错位相减即可。

使用这个递推公式就可在O(n)时间内完成计算。

代码

class Solution(object):
    def maxRotateFunction(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        n = len(A)
        sm = sum(A)
        F = sum([i * A[i] for i in range(n)]) # F0
        maxF = F
        for k in range(1, n):
            F = F + sm - n * A[n - k]
            maxF = max(maxF, F)
        return maxF