LeetCode-396. 旋转函数-Java-easy

题目链接

法一

    /**
     * 数学 + 前缀和
     * 错位相减
     * num = 4(len)
     * f(0):                    a0 * 0 + a1 * 1 + a2 * 2 + a3 * 3
     * f(1):           a3 * 0 + a0 * 1 + a1 * 2 + a2 * 3
     * f(2):  a2 * 0 + a3 * 1 + a0 * 2 + a1 * 3
     * f(n) = f(n - 1) + s(len) - len * a(len - n)
     * @param nums
     * @return
     */
    public int maxRotateFunction(int[] nums) {
        int len = nums.length, sum = 0;
        if(len == 0){
            return 0;
        }
        int[] f = new int[len];
        for(int i = 0; i < len; i++){
            sum += nums[i];
            f[0] += i * nums[i];
        }
        int max = f[0];
        for(int i = 1; i < len; i++){
            f[i] = f[i - 1] + sum - len * nums[len - i];
            max = Math.max(max, f[i]);
        }
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

本地测试

        /**
         * 396. 旋转函数
         */
        lay.showTitle(396);
        Solution396 sol396 = new Solution396();
        int[] nums396 = new int[]{4,3,2,6};
        System.out.println(sol396.maxRotateFunction(nums396));
1
2
3
4
5
6
7