 数学递推)
LeetCode 396. 旋转函数（Rotate Function）详解：从暴力到 O(N) 数学递推
一、题目描述
给定一个长度为n的整数数组nums。
假设arrk是数组nums顺时针旋转 k 个位置后的数组，我们定义nums的旋转函数F为：
F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]要求返回F\(0\), F\(1\), \.\.\., F\(n\-1\)中的最大值。
题目约束条件：
n == nums\.length1 \<= n \<= 10^5\-100 \<= nums\[i\] \<= 100答案保证符合 32 位整数范围
二、示例分析
示例 1
输入: nums = [4,3,2,6] 输出: 26详细计算过程：
F(0) = 0*4 + 1*3 + 2*2 + 3*6 = 0 + 3 + 4 + 18 = 25 F(1) = 0*6 + 1*4 + 2*3 + 3*2 = 0 + 4 + 6 + 6 = 16 F(2) = 0*2 + 1*6 + 2*4 + 3*3 = 0 + 6 + 8 + 9 = 23 F(3) = 0*3 + 1*2 + 2*6 + 3*4 = 0 + 2 + 12 + 12 = 26 最大值 = 26示例 2
输入: nums = [100] 输出: 0只有一种旋转方式，F\(0\) = 0\*100 = 0，因此结果为 0。
三、解题思路：暴力法（直观但不可行）
3.1 思路原理
最直观的解题方式：枚举所有旋转位置k（0到n\-1），每次构建顺时针旋转后的新数组，按照题目定义计算当前F\(k\)，最终遍历得到所有值的最大值。
复杂度缺陷：单次计算F\(k\)需要O\(n\)时间，总共枚举n次，整体时间复杂度为O(n2)O(n^2)O(n2)。当n=10^5时，计算量高达10^10，会直接超时，无法通过大数据用例。
该方法仅用于理解题目逻辑，不适合正式提交。
3.2 暴力法完整代码
fromtypingimportListclassSolution:defmaxRotateFunction_bruteforce(self,nums:List[int])->int:n=len(nums)max_val=float('-inf')forkinrange(n):# 构建顺时针旋转 k 次后的数组：后k位移到最前ifk==0:rotated=numselse:rotated=nums[-k:]+nums[:-k]# 按定义计算当前 F(k)cur=0foriinrange(n):cur+=i*rotated[i]# 更新最大值max_val=max(max_val,cur)returnmax_val# 测试代码if__name__=="__main__":sol=Solution()print(sol.maxRotateFunction_bruteforce([4,3,2,6]))# 输出 26print(sol.maxRotateFunction_bruteforce([100]))# 输出 0四、数学递推优化（O(N) 最优解法）
4.1 核心公式推导
想要通过海量数据测试，必须将时间复杂度优化至线性级O(n)O(n)O(n)。核心思路是：寻找相邻两次旋转函数的递推关系，消除重复计算。
设数组长度为n，数组所有元素总和为S = sum\(nums\)。
先列出基础公式：
F(0)=0⋅nums[0]+1⋅nums[1]+2⋅nums[2]+...+(n−1)⋅nums[n−1]F(0) = 0 \cdot nums[0] + 1 \cdot nums[1] + 2 \cdot nums[2] + ... + (n-1) \cdot nums[n-1]F(0)=0⋅nums[0]+1⋅nums[1]+2⋅nums[2]+...+(n−1)⋅nums[n−1]
数组顺时针旋转1次后，新数组为：\[nums\[n\-1\], nums\[0\], nums\[1\], \.\.\., nums\[n\-2\]\]
此时旋转函数为：
F(1)=0⋅nums[n−1]+1⋅nums[0]+2⋅nums[1]+...+(n−1)⋅nums[n−2]F(1) = 0 \cdot nums[n-1] + 1 \cdot nums[0] + 2 \cdot nums[1] + ... + (n-1) \cdot nums[n-2]F(1)=0⋅nums[n−1]+1⋅nums[0]+2⋅nums[1]+...+(n−1)⋅nums[n−2]
4.2 差值分析与公式化简
对比F\(0\)和F\(1\)可以发现规律：
除了被移到首位的末尾元素nums\[n\-1\]，其余所有元素的权重系数全部 +1；而nums\[n\-1\]的权重从n\-1直接降为 0。
权重全部+1带来的总增量为：S \- nums\[n\-1\]
末尾元素权重清零带来的总减量为：\(n\-1\) \* nums\[n\-1\]
合并化简可得：
F(1)=F(0)+S−n⋅nums[n−1]F(1) = F(0) + S - n \cdot nums[n-1]F(1)=F(0)+S−n⋅nums[n−1]
4.3 通用递推公式
推广到任意旋转次数k，每次旋转都会将当前数组的末尾元素移至首位，可得通用递推公式：
F(k)=F(k−1)+S−n×nums[n−k]F(k) = F(k-1) + S - n \times nums[n-k]F(k)=F(k−1)+S−n×nums[n−k]
公式核心解读：
\+S：所有元素权重统一+1，整体总和增加数组总和\- n \* nums\[n\-k\]：被移到首位的元素，损失了n倍的自身数值，是旋转带来的固定差值
4.4 图解辅助理解
假设原数组nums = \[a₀, a₁, a₂, \.\.\., aₙ₋₁\]，总和S = sum\(nums\)
F(0) = 0·a₀ + 1·a₁ + 2·a₂ + ... + (n-1)·aₙ₋₁ F(1) = F(0) + S - n·aₙ₋₁ F(2) = F(1) + S - n·aₙ₋₂ ... F(k) = F(k-1) + S - n·nums[n-k]五、完整代码实现
5.1 标准优化版（推荐提交）
fromtypingimportListclassSolution:defmaxRotateFunction(self,nums:List[int])->int:n=len(nums)# 计算数组元素总和total=sum(nums)# 计算初始旋转函数 F(0)F=0fori,numinenumerate(nums):F+=i*num# 记录最大值，初始为 F(0)max_F=F# 递推计算 F(1) ~ F(n-1)forkinrange(1,n):F=F+total-n*nums[n-k]max_F=max(max_F,F)returnmax_F5.2 Python 简洁写法（负数索引优化）
利用 Python 负数索引特性，nums\[\-i\]等价于nums\[n\-i\]，代码更简洁优雅：
fromtypingimportListclassSolution:defmaxRotateFunction(self,nums:List[int])->int:n=len(nums)total=sum(nums)# 列表推导式快速计算 F(0)F=sum(i*numfori,numinenumerate(nums))max_F=F# 递推所有旋转结果foriinrange(1,n):F=F+total-n*nums[-i]max_F=max(max_F,F)returnmax_F5.3 完整测试代码（多用例验证）
fromtypingimportListclassSolution:defmaxRotateFunction(self,nums:List[int])->int:n=len(nums)total=sum(nums)F=sum(i*numfori,numinenumerate(nums))max_F=Fforiinrange(1,n):F=F+total-n*nums[-i]max_F=max(max_F,F)returnmax_F# 批量测试用例if__name__=="__main__":sol=Solution()# 基础示例nums1=[4,3,2,6]print(f"示例1输出:{sol.maxRotateFunction(nums1)}")# 26nums2=[100]print(f"示例2输出:{sol.maxRotateFunction(nums2)}")# 0# 拓展测试用例nums3=[1,2,3,4,5,6,7,8,9,10]print(f"测试用例3输出:{sol.maxRotateFunction(nums3)}")# 330nums4=[-2,0,5,-1,2]print(f"测试用例4输出:{sol.maxRotateFunction(nums4)}")# 16六、复杂度分析
| 解题方法 | 时间复杂度 | 空间复杂度 | 是否可AC |
|---|---|---|---|
| 暴力模拟法 | O(n2)O(n^2)O(n2) | O(n)O(n)O(n) | 否（超时） |
| 数学递推优化法 | O(n)O(n)O(n) | O(1)O(1)O(1) | 是（最优解） |
优化解法详解：
时间：计算数组总和、初始
F\(0\)、递推遍历均为单次线性遍历，总复杂度O(n)O(n)O(n)空间：仅使用常数临时变量，未开辟额外数组，原地计算，空间复杂度O(1)O(1)O(1)
七、核心要点总结
核心递推公式：F(k)=F(k−1)+sum(nums)−n×nums[n−k]F(k) = F(k-1) + sum(nums) - n \times nums[n-k]F(k)=F(k−1)+sum(nums)−n×nums[n−k]，是解题的关键
旋转本质：顺时针旋转一次 = 末尾元素移至首位，其余元素权重+1
边界自适应：当数组长度
n=1时，递推循环不会执行，直接返回F\(0\)=0，无需额外判断数值兼容：公式支持数组正负元素，无需特殊处理，适配题目所有数据范围
优化思想：算法常见优化思路，通过状态递推剔除重复计算，将平方级复杂度降为线性级
八、拓展思考
若题目改为逆时针旋转，递推公式需要如何调整？
若权重不再是
0、1、2\.\.\.n\-1的连续递增序列，该递推优化思路是否仍然适用？
此类旋转带权求和题型，核心逻辑均为：挖掘相邻操作的状态差值，用数学公式替代暴力模拟，是算法刷题的经典优化模型。
