LeetCode 解題筆記：396. Rotate Function

作者：王一哲
日期：2026年8月7日


LeetCode 題目連結：396. Rotate Function

解題想法

中等難度題。題目給一個長度為 $n$ 的陣列 $nums$，並定義 $arr_k$ 為 $nums$ 向右平移 $k$ 格，求以下的方程式最大值。 $$ F(k) = 0 \times arr_k [0] + 1 \times arr_k [1] + 2 \times arr_k [2] + \dots + (n-1) \times arr_k [n-1] $$ 這題考動態規畫，假設 $nums$ 長度為 $4$ 先列出前幾項 $F(k)$ 找規律 $$ \begin{align*} F(0) &= 0 \times nums[0] + 1 \times nums[1] + 2 \times nums[2] + 3 \times nums[3] \\ F(1) &= 0 \times nums[3] + 1 \times nums[0] + 2 \times nums[1] + 3 \times nums[2] \\ F(2) &= 0 \times nums[2] + 1 \times nums[3] + 2 \times nums[0] + 3 \times nums[1] \\ F(3) &= 0 \times nums[1] + 1 \times nums[2] + 2 \times nums[3] + 3 \times nums[0] \end{align*} $$ 定義 $isum = \sum nums[i]$。將以上相鄰兩式相減可得 $$ \begin{align*} F(1) - F(0) &= nums[0] + nums[1] + nums[2] - 3 \times nums[3] = isum - 4 \times nums[3] \\ F(2) - F(1) &= nums[3] + nums[0] + nums[1] - 3 \times nums[2] = isum - 4 \times nums[2] \\ F(3) - F(2) &= nums[2] + nums[3] + nums[0] - 3 \times nums[1] = isum - 4 \times nums[1] \\ \end{align*} $$ 規律為 $$ F(i) = F(i-1) + isum - n \times nums[n-i] $$ 由於計算 $F(i)$ 時只會用到 $F(i-1)$ 的值，可以用一個變數 $dp$ 儲存資料，不需要用陣列。解題時，先計算加總 $isum$ 及 $dp = F(0)$，將答案 $ans$ 先設為 $dp$，再用 for 迴圈依序更新 $i = 1$ 到 $i = n-1$ 對應的 $dp$ 值，同時更新 $ans$。

Python 程式碼

Runtime: 143 ms, beats 52.49%. Memory: 31.37 MB, beats 18.77%.

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        n = len(nums)
        isum, dp = 0, 0  # 加總，F(k)
        for i, num in enumerate(nums):
            isum += num
            dp += i * num
        ans = dp  # 答案
        for i in range(1, n):  # 更新 i = 1 ~ n-1
            dp = dp + isum - n * nums[n-i]
            ans = max(ans, dp)
        return ans

C++ 程式碼

計算 $dp$ 的過程如果用 int 會溢位。Runtime: 4 ms, beats 37.82%. Memory: 100.36 MB, beats 30.30%.

class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        int n = (int)nums.size();
        long isum = 0, dp = 0;
        for(int i = 0; i < n; i++) {
            isum += nums[i];
            dp += i * nums[i];
        }
        long ans = dp;
        for(int i = 1; i < n; i++) {  // 更新 i = 1 ~ n-1
            dp = dp + isum - n * nums[n-i];
            ans = max(ans, dp);
        }
        return ans;
    }
};

C 語言程式碼

計算 $dp$ 的過程如果用 int 會溢位。Runtime: 0 ms, beats 100.00%. Memory: 16.49 MB, beats 81.82%.

int maxRotateFunction(int* nums, int numsSize) {
    long isum = 0, dp = 0;
    for(int i = 0; i < numsSize; i++) {
        isum += nums[i];
        dp += i * nums[i];
    }

    long ans = dp;
    for(int i = 1; i < numsSize; i++) {
        dp = dp + isum - numsSize * nums[numsSize - i];
        if (dp > ans) ans = dp;
    }
    return ans;
}