解题思路
- 当本题的
len(A)<=1时候，结果一定为零。 - 当
len(A)>1时，我们可以得到递推公式即F(k)=F(k-1)+len(A)*A[len(A)-k]+sum(A)。 - 其中最大的值，即为所求。
代码
class Solution(object): def maxRotateFunction(self, A): """ :type A: List[int] :rtype: int """ long = len(A) sum_1 = sum(A) print(sum_1) if long <= 1: return 0 for i in range(long): sums = 0 if i == 0: #计算没有滑动的F(0) memeory = sum([ A[j] * j for j in range(long)]) maxs = memeory else: sums = sum_1 - long * A[long-i] + memeory maxs = max(sums,maxs) memeory = sums return max(maxs,memeory)
另一种方法，时间复杂度有点高，好理解。
class Solution(object): def maxRotateFunction(self, A): """ :type A: List[int] :rtype: int """ i = 0 list1 = [] if A == []: return 0 while i < len(A): sums = 0 for j in range(len(A)): sums += j * A[j] list1.append(sums) A.insert(0,A.pop()) i += 1 return max(list1)
