🌕🌕 396. 旋转函数

难度: 🌕🌕

问题描述

---

解法

class Solution {
    public int maxRotateFunction(int[] nums) {
        // 思路：
        // 找规律
        // 例 [4, 3, 2, 6]
        // f(0) = 0*4 + 1*3 + 2*2 + 3*6
        // f(1) = 1*4 + 2*3 + 3*2 + 0*6 
        // f(2) = 2*4 + 3*3 + 0*2 + 1*6
        // f(3) = 3*4 + 0*3 + 1*2 + 2*6
        // 可以看出，f(x) = f(x - 1) + sum - len*[len - x]
        // 因此可以递推得到最终结果
        int len = nums.length;
        // 首先遍历一遍求 sum
        int sum = 0;
        for(int i: nums) {
            sum += i;
        }
        // 求 f(0)
        int a = 0;
        for(int i = 0; i < len; i ++) {
            a += i * nums[i];
        }
        // 递推
        int res = a;
        for(int i = 1; i < len; i ++) {
            // 根据前一个 f(x - 1) 得到 f(x)
            int b = a + sum - len * nums[len - i];
            res = Math.max(res, b);
            a = b;
        }
        return res;
    }
}

---

输出