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 位参与者
来源: linux.do查看原文