1.题目基本信息

1.1.题目描述

假设 arrk 是数组 nums 顺时针旋转 k 个位置后的数组，我们定义 nums 的 旋转函数 F 为：

• F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]

返回 F(0), F(1), ..., F(n-1)中的最大值 。

生成的测试用例让答案符合 32 位 整数。

1.2.题目地址

https://leetcode.cn/problems/rotate-function/description/

2.解题方法

2.1.解题思路

数学，递推公式

2.2.解题步骤

• F(k)=0nums[n-k]+1nums[n-k+1]+...+(k-1)nums[n-1]+knums[0]+...+(n-1)*nums[n-k-1]

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

观察可知:F(k)=F(k-1)+sum(nums)-n*nums[n-k]，最终的题解为max(F(j) for j in range(0,n-1))

3.解题代码

python代码

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        # 思路：数学，递推公式
        # F(k)=0*nums[n-k]+1*nums[n-k+1]+...+(k-1)*nums[n-1]+k*nums[0]+...+(n-1)*nums[n-k-1]
        # F(k-1)=0*nums[n-k+1]+1*nums[n-k+2]+...+(k-2)*nums[n-1]+(k-1)*nums[0]+...+(n-1)*nums[n-k]
        # 观察可知:F(k)=F(k-1)+sum(nums)-n*nums[n-k]，最终的题解为max(F(j) for j in range(0,n-1))
        n = len(nums)
        f = 0
        sum1 = 0
        for i in range(n):
            f += i * nums[i]
            sum1 += nums[i]
        result = f
        for k in range(1, n):
            f += sum1 - n * nums[n - k]
            result = max(result, f)
        return result

c++代码

class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        int n = nums.size();
        int f = 0, sum1 = 0;
        for (int i = 0; i < n; i++) {
            f += i * nums[i];
            sum1 += nums[i];
        }
        int result = f;
        for (int k = 1; k < n; k++) {
            f += sum1 - n * nums[n - k];
            result = max(result, f);
        }
        return result;
    }
};

4.执行结果