396.md

396 Rotate Function

Description

link

---

Solution

F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]
F(k-1) = 0 * Bk-1[0] + 1 * Bk-1[1] + ... + (n-1) * Bk-1[n-1]
       = 0 * Bk[1] + 1 * Bk[2] + ... + (n-2) * Bk[n-1] + (n-1) * Bk[0]

F(k) - F(k-1) = Bk[1] + Bk[2] + ... + Bk[n-1] + (1-n)Bk[0]
              = (Bk[0] + ... + Bk[n-1]) - nBk[0]
              = sum - nBk[0]

F(k) = F(k-1) + sum - nBk[0]

# Bk[0]?
k = 0; B[0] = A[0];
k = 1; B[0] = A[len-1];
k = 2; B[0] = A[len-2];
...

---

Code

O(n)

class Solution:
    def maxRotateFunction(self, A: List[int]) -> int:
        n = len(A)
        
        tmp_sum = 0
        all_sum = 0
        for i in range(n):
            all_sum += A[i]
            tmp_sum += i * A[i]
        
        res = tmp_sum
        for i in range(n):
            tmp_sum = tmp_sum - all_sum + n * A[i]
            res = max(res, tmp_sum)
            
        return res