LeetCode 396中等动态规划
旋转函数 图解题解
这道题到底在问什么
F(k) = 0×arr_k[0] + 1×arr_k[1] + … + (n-1)×arr_k[n-1]，其中 arr_k 是 nums 顺时针旋转 k 格后的数组。返回 F(0)…F(n-1) 中的最大值。直接对每个 k 重新加权求和是 O(n²)，我们要找 O(n) 的递推。
- 输入
- nums=[4,3,2,6]
- 输出
- 26（F(3) 最大）
- 输入
- nums=[100]
- 输出
- 0（单元素只有 F(0)=0）
最优解：一步一步想明白
- 3把这句话记死:「整体加一个 sum，再减掉 n 乘以转到队首的那个元素」。下面每一帧都在套它。
- 4递推需要一个起点，所以第一步先按定义老实算出 F(0)，顺便把所有元素之和 sum 也累出来。下面从下标 0 开始，一个元素一个元素地往里加。
- 5看下标 0 的元素 4（紫色）。它对 F(0) 的贡献是下标乘元素，也就是 0 × 4 = 0，把它加进 F(0)；同时把 4 也累进 sum。左边蓝色是已经算过的，灰色是还没轮到的。
- 6看下标 1 的元素 3（紫色）。它对 F(0) 的贡献是下标乘元素，也就是 1 × 3 = 3，把它加进 F(0)；同时把 3 也累进 sum。左边蓝色是已经算过的，灰色是还没轮到的。
- 7看下标 2 的元素 2（紫色）。它对 F(0) 的贡献是下标乘元素，也就是 2 × 2 = 4，把它加进 F(0)；同时把 2 也累进 sum。左边蓝色是已经算过的，灰色是还没轮到的。
- 8看下标 3 的元素 6（紫色）。它对 F(0) 的贡献是下标乘元素，也就是 3 × 6 = 18，把它加进 F(0)；同时把 6 也累进 sum。左边蓝色是已经算过的，灰色是还没轮到的。
- 9看下标 4 的元素 4（紫色）。它对 F(0) 的贡献是下标乘元素，也就是 4 × 4 = 16，把它加进 F(0)；同时把 4 也累进 sum。左边蓝色是已经算过的，灰色是还没轮到的。
- 10五个元素都加完:F(0) = 41，sum = 19。F(0) 既是第一个候选答案，也是后面递推的起点，所以当前最大 ans 先记成 41。接下来不再重新加权求和，全靠递推一格一格滚。
- 11先看清旋转一格发生了什么:排在最后、系数 4 的红色元素 nums[4]=4 会转到最前面变成系数 0；其余每个元素系数都加 1。系数集体加 1 = 整体加 sum，红色元素从 4× 变 0× = 减掉 n×它。这就是递推式的来历。
- 12第 1 次旋转:这次转到队首的是下标 4 的红色元素 4。套递推式,先把数字代进去:上一帧的 F(0)=41，加上 sum=19，再减掉 n × nums[4] = 5 × 4。
- 13把它算干净:41 + 19 先得 60，再减 5 × 4 = 20，于是 F(1) = 40。注意这一步只做了一次加法和一次减法,O(1) 就推出来了,完全没有重新加权求和。
- 14拿 F(1)=40 和当前最大 41 比:没超过,最大答案保持 41 不动,继续往后滚。
- 15第 2 次旋转:这次转到队首的是下标 3 的红色元素 6。套递推式,先把数字代进去:上一帧的 F(1)=40，加上 sum=19，再减掉 n × nums[3] = 5 × 6。
- 16把它算干净:40 + 19 先得 59，再减 5 × 6 = 30，于是 F(2) = 29。注意这一步只做了一次加法和一次减法,O(1) 就推出来了,完全没有重新加权求和。
- 17拿 F(2)=29 和当前最大 41 比:没超过,最大答案保持 41 不动,继续往后滚。
- 18第 3 次旋转:这次转到队首的是下标 2 的红色元素 2。套递推式,先把数字代进去:上一帧的 F(2)=29，加上 sum=19，再减掉 n × nums[2] = 5 × 2。
- 19把它算干净:29 + 19 先得 48，再减 5 × 2 = 10，于是 F(3) = 38。注意这一步只做了一次加法和一次减法,O(1) 就推出来了,完全没有重新加权求和。
- 20拿 F(3)=38 和当前最大 41 比:没超过,最大答案保持 41 不动,继续往后滚。
- 21第 4 次旋转:这次转到队首的是下标 1 的红色元素 3。套递推式,先把数字代进去:上一帧的 F(3)=38，加上 sum=19，再减掉 n × nums[1] = 5 × 3。
- 22把它算干净:38 + 19 先得 57，再减 5 × 3 = 15，于是 F(4) = 42。注意这一步只做了一次加法和一次减法,O(1) 就推出来了,完全没有重新加权求和。
- 23拿 F(4)=42 和当前最大 41 比:42 更大,刷新最大答案,ans 变成 42（整排标绿表示出现了新的最大）。
- 24全部 5 个 F 值滚完:F(0) 到 F(4) 分别是 41、40、29、38、42，其中最大的是 F(4) = 42，这就是答案。回头看,我们只在开头老实算了一次 F(0)，之后每个 F(k) 都是 O(1) 推出来的,整体 O(n)。
⚠️ 容易写错的地方
✗ 错：搞错转到队首的是哪个元素
✓ 对：第 k 次旋转转到队首的是 nums[n-k]
顺时针旋转 k 格,原数组末尾起第 k 个元素跑到最前
✗ 错：忘了先算 F(0) 当起点
✓ 对：递推必须有 base，先按定义算出 F(0)
F(k) 依赖 F(k-1)，没有 F(0) 链条接不上
✗ 错：把递推写成减 nums[n-k] 而漏了 n
✓ 对：是 − n × nums[n-k]，系数差恰好是 n
该元素系数从 n-1 变 0，差 (n-1)，整体又 +sum 含它一份,合起来减 n 份
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def maxRotateFunction(self, nums: List[int]) -> int:
f = sum(i * v for i, v in enumerate(nums))
n, s = len(nums), sum(nums)
ans = f
for i in range(1, n):
f = f + s - n * nums[n - i]
ans = max(ans, f)
return ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int maxRotateFunction(vector<int>& nums) {
int f = 0, s = 0, n = nums.size();
for (int i = 0; i < n; ++i) {
f += i * nums[i];
s += nums[i];
}
int ans = f;
for (int i = 1; i < n; ++i) {
f = f + s - n * nums[n - i];
ans = max(ans, f);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int maxRotateFunction(int[] nums) {
int f = 0;
int s = 0;
int n = nums.length;
for (int i = 0; i < n; ++i) {
f += i * nums[i];
s += nums[i];
}
int ans = f;
for (int i = 1; i < n; ++i) {
f = f + s - n * nums[n - i];
ans = Math.max(ans, f);
}
return ans;
}
}复杂度
时间
O(n)
算 F(0) 一遍，递推再一遍
空间
O(1)
只用 f、s、ans 几个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 旋转函数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
怎么想到这条递推的？+
不要去硬算每个旋转后的数组,而是盯住「相邻两次旋转之间 F 的变化」。把 F(k) 和 F(k-1) 写出来逐项作差,会发现绝大多数项系数只差 1（贡献一份 sum），只有一个元素从最大系数跳回 0（贡献 −n×它）。把变化量算出来,递推就自然浮现。这是「相邻状态作差」类优化的通用套路。
答案会不会溢出？+
题目保证答案落在 32 位整数范围内,所以 C++/Java 用 int 即可。但若元素绝对值大、n 大,中间的 f 也可能接近边界,稳妥起见可用 long 累加再返回,Python 没有溢出问题。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 旋转函数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。