LeetCode 396. 旋转函数题目要点定义 F(k) 0arr_k[0] 1arr_k[1] … (n-1)*arr_k[n-1]其中 arr_k 是把 nums 顺时针旋转 k 位即把末尾 k 个元素搬到前面后的数组。求 F(0)…F(n-1) 的最大值。核心推导递推关系直接暴力算每个 F(k) 是 O(n²)会超时。关键是找 F(k) 和 F(k-1) 的关系。以 k1 为例F(0) 0*nums[0] 1*nums[1] ... (n-2)*nums[n-2] (n-1)*nums[n-1] F(1) 0*nums[n-1] 1*nums[0] 2*nums[1] ... (n-1)*nums[n-2]对比可见F(1) 相比 F(0)前 n-1 个元素系数都 1而 nums[n-1] 的系数从 n-1 变成 0。于是F(1) F(0) (nums[0] nums[1] ... nums[n-2]) - (n-1)*nums[n-1] F(0) (sum - nums[n-1]) - (n-1)*nums[n-1] F(0) sum - n * nums[n-1]推广得到通式F(k) F(k-1) sum − n × nums[n−k]这样从 F(0) 出发递推即可整体 O(n)。Java 实现classSolution{publicintmaxRotateFunction(int[]nums){intnnums.length;longsum0;// 数组总和longf0;// 当前 F(0)for(inti0;in;i){sumnums[i];f(long)i*nums[i];}longmaxf;// 依次递推 F(1), F(2), ..., F(n-1)for(intk1;kn;k){ffsum-(long)n*nums[n-k];maxMath.max(max,f);}return(int)max;}}注意用 longn 最大 10⁵F(0) 量级约为 n²×100 ≈ 10¹²远超 int 范围中间值同样需要 long。· 时间复杂度O(n)· 空间复杂度O(1)测试用例publicstaticvoidmain(String[]args){SolutionsolnewSolution();System.out.println(sol.maxRotateFunction(newint[]{4,3,2,6}));// 26System.out.println(sol.maxRotateFunction(newint[]{100}));// 0}验证 [4,3,2,6]F(0) 0*4 1*3 2*2 3*6 25 F(1) F(0) 15 - 4*6 16 F(2) F(1) 15 - 4*2 23 F(3) F(2) 15 - 4*3 26 ← 最大易错点旋转方向题目按「末尾元素往前搬」定义对应递推里减去的是 nums[n-k]若用其他旋转定义减去的下标会不同。溢出务必用 long 存储 sum 和 f。n 1 的边界循环不执行直接返回 F(0)0代码自然覆盖。与其他解法的对比解法 时间 说明暴力逐次旋转计算 O(n²) 超时不推荐递推本解 O(n) 最优代码短推荐
