396.-rotate-function.md

396. Rotate Function

• Medium

• You are given an integer array nums of length n.

  Assume arrk to be an array obtained by rotating nums by k positions clock-wise. We define the rotation function F on nums as follow:

  • F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1].

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

  The test cases are generated so that the answer fits in a 32-bit integer.

Analysis

Given the value of A(n) at any time, it is easy for us to calculate the value of A(n+1). Therefore we can simply go through all the values of A(i) and see which one is the maximum.

class Solution(object):
    def maxRotateFunction(self, A):
        r = curr = sum(i * j for i,j in enumerate(A))
        s = sum(A)
        k = len(A)
        while A:
            curr += s - A.pop() * k
            r = max(curr, r)
        return r