递归公式：求解《396. 旋转函数》

用递推归纳法，求解《396. 旋转函数》

递推公式

f(k) = f(k - 1) + sum - n * nums[n - k] // 如上图所示

例题

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 位 整数。

答案

var maxRotateFunction = function(nums) {
  const n = nums.length
  let sum = f = 0
  for (let i = 0; i < n; i++) {
    sum += nums[i]
    f += i * nums[i]
  }
  let r = f
  for (let i = 1; i < n; i++) {
    f += sum - n * nums[n - i]
    if (f > r) r = f
  }
  return r
};

func maxRotateFunction(nums []int) int {
  n, sum, f := len(nums), 0, 0
  for i, v := range nums {
    sum += v
    f += v * i
  }
  r := f
  for i := 1; i < n; i++ {
    f += sum - n * nums[n - i]
    if f > r {
      r = f
    }
  }
  return r
}

class Solution {
    function maxRotateFunction($nums) {
      $sum = $f = 0;
      foreach ($nums as $i => $v) {
        $sum += $v;
        $f += $v * $i;
      }
      $n = count($nums);
      $r = $f;
      for ($i = 1; $i < $n; $i++) {
        $f += $sum - $n * $nums[$n - $i];
        if ($f > $r) $r = $f;
      }
      return $r;
    }
}