leetcode 396. Rotate Function | 396. 旋转函数（错位相减）

桃扇骨 2022-09-01 14:49 124阅读 0赞

## 题目 ##

[https://leetcode.com/problems/rotate-function/][https_leetcode.com_problems_rotate-function]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

参考了评论区 [O(n)错位相减][O_n] 的题解。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

class Solution { 
        public int maxRotateFunction(int[] nums) { 
            int sum = 0;
            for (int n : nums) { 
                sum += n;
            }
    
            int L = nums.length;
            int[] f = new int[L];
            for (int i = 0; i < L; i++) {  // init f(0)
                f[0] += i * nums[i];
            }
            int max = f[0];
            for (int i = 1; i < L; i++) { 
                f[i] = f[i - 1] + sum - L * nums[L - i];
                max = Math.max(max, f[i]);
            }
            return max;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_rotate-function]: https://leetcode.com/problems/rotate-function/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/9a60661e48e54522b81120da692b4075.png
[O_n]: https://leetcode-cn.com/problems/rotate-function/solution/oncuo-wei-xiang-jian-by-xiaohu9527-ftzh/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/c0fa4d842134404691ff7323a60ce918.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/27b9e3878d014950be28226df67bf87d.png