力扣 LeetCode 396. 旋转函数 - 力扣（LeetCode） 396. 旋转函数 - 给定一个长度为 n 的整数数组 nums 。 假设 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: 输入: nums =... 思路 看了一下示例，感觉是可以直接进行递推的，从 F(n-1) 推出 F(n) ，不过得找一下规律。 正好题目给了示例 1，重新排版一下可以看到： F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) 如果要从 F(0) 推出 F(1) ，相当于把 F(0) 除最后一个数字外的份数全部加一份 ， F(1) 到 F(2) 也是类似。 份数全部加一份其实很类似直接加上整个 nums 的和，但是要忽略最后一个数字，因此可以在加上整个数组的和后减去最后一个数字的 n 份。 这样一来递推思路就很清晰了。 代码 class Solution { public: int maxRotateFunction(vector<int>& nums) { // 感觉从 F(0), F(1), ..., F(n-1) 能观察出规律 // F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) // F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) // F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) // // 可以看到每次落到末尾的数字，下一个 F 处就会归零 // 其他数字的份数每次都会 + 1 // F(k) 相当于 F(k-1) 加上 [整个 nums 的和] 一份，然后再减去 [F(k-1) 时最后一个数字] 的 n 份 int n=nums.size(); // 先算出 F(0)，以及整个 nums 的和 int f=0; int nSum=0; for(int i=0;i<n;i++){ f+=i*nums[i]; nSum+=nums[i]; } int res=f; // 开始递推 for(int i=1;i<n;i++){ // 加上一份和 f+=nSum; // 减去 n 份最后一个数字 f-=n*nums[n-i]; res=max(res,f); } return res; } }; 2 个帖子 - 2 位参与者 阅读完整话题