Problem statement

https://leetcode.com/problems/rotate-function/

Solution

Let us evaluate F(0) in O(n) time. We can see, that F(1) = F(0) + S - n * A[-1], F(2) = F(1) + S - n * A[-2] and so on. So, we can evaluate each next F(i) in O(1)` and update maximum.

Complexity

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

Code

class Solution:
    def maxRotateFunction(self, A):
        n, s = len(A), sum(A)
        F = sum(x*y for x, y in zip(A, range(n)))
        ans = F
        for i in range(1, n):
            F += s - n*A[-i]
            ans = max(ans, F)
        return ans