動機

推導怎麼那麼難想，脫離高中太久，忘了還可以用相減去看

Problem

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:

    t
  • 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.

 

Example 1:

Input: nums = [4,3,2,6]Output: 26Explanation:F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

Example 2:

Input: nums = [100]Output: 0

 

Constraints:

    t
  • n == nums.length
    • t
  • 1 <= n <= 105
    • t
  • -100 <= nums[i] <= 100

Sol

f(0) = 0A + 1B + 2C + 3D
f(1) = 3A + 0B + 1C + 2D
f(2) = 2A + 3B + 0C + 1D

f(1)-f(0) = 3A -1B - 1C - 1D
f(2)-f(1) = -1A + 3B - 1C -1D

sum = A + B + C + D
f(1) = f(0) - sum + 4A
f(2) = f(1) - sum + 4B
f(n) = f(n-1) - sum + len(arr)*arr[n-1]

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:     
        cnt = sum(nums)
        @cache
        def f(n):
            if n == 0:
                return sum([i*nums[i] for i in range(len(nums))])
            else:
                return f(n-1) - cnt + len(nums)*nums[n-1]
        
        return max([f(i) for i in range(len(nums))])