First thought would be an N square solution;

Then find out that

f[0] = 0 * A[0] + 1 * A[1] + .... + (n-1) * A[n-1]

f[1] = 1 * A[0] + 2 * A[1] + .... + (n-1) * A[n-2] + 0 * A[n-1] = f[0] + sum(A) - n * A[n-1]

f[2] = 2 * A[0] + 3 * A[2] + ... + 0 * A[n-2] + 1 * A[n-1] = f[1] + sum(A) - n * A[n-2]

.....

Time complexity is O(n), space complexity is O(1)

Here is the code:

```
def maxRotateFunction(A):
N = len(A)
res = 0
f = sum(A)
for i in xrange(N):
res += i * A[i]
cur = res
for i in xrange(1, N):
cur = cur + f - N * A[N-i]
res = max(res, cur)
return res
```