题目
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
