题目

给定一个长度为 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 = [4,3,2,6]
输出: 26
解释:
F(0) = (0 4) + (1 3) + (2 2) + (3 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 6) + (1 4) + (2 3) + (3 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 2) + (1 6) + (2 4) + (3 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 3) + (1 2) + (2 6) + (3 4) = 0 + 2 + 12 + 12 = 26
所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 。

示例 2:

输入: nums = [100]
输出: 0

提示:

n == nums.length
1 <= n <= 10^5
-100 <= nums[i] <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-function
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

对于nums = [4,3,2,6]，观察F(0)和F(1)之间的差别：

  1. // 原数组   4 3 2 6
  2. // 旋转1 位 6 4 3 2
  3. // 下标    0 1 2 3
  4. // F(0) =     0*4+1*3+2*2+3*6
  5. // F(1) = 0*6+1*4+2*3+3*2

可以发现，4、3、2三个数各自多加了一次，6少了三次。可以推出，旋转k次后，前n-k个数多加k次，其余k个数少加n-k次。求前n-k个数的和后k个数的和可以使用前缀和数组。

前面说的少加多加都是基于数组不旋转时元素值和索引乘积之和而言的。

以为自己的方法还不错，结果官解(见「这里」)是O(1)空间，还得进步啊…

代码

  1. class Solution {
  2.     public int maxRotateFunction(int[] nums) {
  3.         int n = nums.length;
  4.         int[] preSum = new int[n + 1];
  5.         for (int i = 1; i < n + 1; i++) {
  6.             preSum[i] = preSum[i - 1] + nums[i - 1];
  7.         }
  8.         // 不旋转时的和，即F(0)
  9.         int sum = 0;
  10.         for (int i = 0; i < n; i++) {
  11.             sum += i * nums[i];
  12.         }
  13.         int ans = sum;
  14.         // 分别旋转1次到n-1次
  15.         for (int i = 1; i < n; i++) {
  16.             // 合并preSum[n - i]后，可以化简为ans = Math.max(ans, sum + preSum[n - i] * n - preSum[n] * (n - i))
  17.             // 然后这里也可以看出，preSum[n]就是所有元素的和，可以先求出来；preSum[n - i]可以在循环中计算，因此就不需要另外的数组了
  18.             ans = Math.max(ans, sum + preSum[n - i] * i - (preSum[n] - preSum[n - i]) * (n - i));
  19.         }
  20.         return ans;
  21.     }
  22. }