力扣每日一题2022-04-22中等题：旋转函数

旋转函数

• • 题目描述
  • 思路
  • • 迭代
    • • Python实现
      • Java实现

---

题目描述

旋转函数

---

思路 迭代

记nums的元素之和为numSum。根据公式，可以得到：

• F(0) = 0nums[0] + 1nums[1] + … + (n-1)*nums[n-1]
• F(1) = 1nums[0] + 2nums[1] + … + 0*nums[n-1] = F(0) + numSum - n * nums[n-1]
  由此可以得到，当1<=k F ( k ) = F ( k − 1 ) + n u m S u m − n ∗ n u m s [ n − k ] F(k) = F(k-1) + numSum - n*nums[n-k] F(k)=F(k−1)+numSum−n∗nums[n−k]
  不断迭代计算出不同的F(K)，并求出最大值。

Python实现

class Solution:
    def maxRotateFunction(self, nums: List[int]) -> int:
        f, n, numSum = 0, len(nums), sum(nums)
        for i, num in enumerate(nums):
            f += i * num
        ans = f
        for i in range(n-1, 0, -1):
            f = f + numSum - n * nums[i]
            ans = max(ans, f)
        return ans

Java实现

class Solution {
    public int maxRotateFunction(int[] nums) {
        int f = 0, n = nums.length, numSum = Arrays.stream(nums).sum();
        for (int i = 0; i < n; i++) {
            f += i * nums[i];
        }
        int res = f;
        for (int i = n - 1; i > 0; i--) {
            f += numSum - n * nums[i];
            res = Math.max(res, f);
        }
        return res;
    }
}