题目
给定一个序列
a[1..n]，把它切成若干段（通常是
恰好 k 段），使
各段内部方差之和最大。
输入: a = [2, 8, 3, 9, 4, 7]，k = 2
输出: 14.6875
解释: 最优切点在第 2 个元素之后：[2,8] 方差 9.00 + [3,9,4,7] 方差 5.6875
这是数据/算法面试里的经典 DP（也常以「最小化」的面目出现）。它有两个值得挖的点：
答案可以违背直觉（切成两段常常比不切更大），以及
性能全压在一条前缀和公式上（不会写就是
O(n^3)）。
一、核心洞察：切成两段，反而更大
先说这道题最反直觉的地方。主例
[2, 8, 3, 9, 4, 7] 的
全序列方差只有 6.92，而切成两段之后最大能到
14.69 —— 切分让方差和翻了一倍多。
为什么？方差度量的是「到均值的距离」。整序列的均值是 5.5，
8 和
3 一上一下互相抵消；切成
[2,8] 和
[3,9,4,7] 之后，两段各自有均值（5.00 与 5.75），
原本互相抵消的偏离被单独放大了。所以「切得越碎方差和越小」是错的本能 —— 本题要的是最大，而最大往往出现在
段内很散、段间均值接近的切法上。
顺便立一个永远成立的恒等式，它能帮你判断什么时候两种问法等价：
离差平方和分解：SS_total = SS_within + SS_between（总平方和 = 组内平方和 + 组间平方和）。
SS 是「偏离均值的平方之和」。当各段
等长时，
组内方差和 = SS_within / 段长，于是「最大化组内方差和」严格等价于「最小化组间」—— 也就是
让各段均值尽量靠近。段长不相等时这个换算不成立（每段除的各是个的长度），但 DP 照做，只是少了一条捷径。
二、拆解：一阶/二阶前缀和，O(1) 算段方差
DP 的形式很直接：
dp[i][j] = max_{k} dp[k][j-1] + var(k+1 .. i)
dp[i][1] = var(1 .. i)
dp[0][0] = 0
答案 = dp[n][k]
k = 2 时它退化成一次扫描：枚举切点
i，取
var(1..i) + var(i+1..n) 的最大值 —— 这正是 DP 的第一层，后面
j 层是同一个式子往上叠。
性能的关键在
var(k+1..i) 怎么算。每换一个切点就重算一遍区间均值方差是
O(n)，总复杂度
O(n^2 k) 里还藏着一个
O(n)；用
一阶和二阶前缀和可以压到
O(1)：
S1[i] = a[1] + ... + a[i] # 一阶前缀和
S2[i] = a[1]^2 + ... + a[i]^2 # 二阶前缀和
段 [l+1, i]，长度 len = i - l：
sum = S1[i] - S1[l]
mean = sum / len
var = (S2[i] - S2[l]) / len - mean * mean # E[x^2] - E[x]^2
E[x^2] - E[x]^2 就是总体方差的定义式。有了它，DP 的内层就是两次数组访问加一次乘减。
三、动画怎么看
动画画的是
k = 2 这一层：序列画成柱子，
两条虚线是两段的均值线，橙色竖虚线是当前切点。
- 均值线：方差就是柱子到均值线的距离平方的平均 —— 线拉得越开、各段内部越散，两段方差和越大；
- 切点线：从左到右扫，每扫一个切点，两个统计筹码刷新一次；
- 合计筹码：金色高亮 = 目前最优；扫到终点定格在「最优切点 2 / 合计 14.69」。
值得盯的帧是切点 2 和切点 4：切点 2 的左段
[2,8] 方差高达 9.00，右段 5.69；切点 4 左段 9.25、右段只有 2.25，合计反而降到 11.50。
最优解不在「看起来最该切」的地方 —— 这就是不能贪心的直接证据。
四、完整推演表
主例
[2, 8, 3, 9, 4, 7]，
k = 2（对应动画的 5 个切点帧 + init + done，共 7 帧）：
最后一行值得多说一句：右段只剩一个元素，方差必然是 0。
单点段的方差恒为 0，这是
k = n 时答案退化为 0 的原因，也是边界情况里最容易被忘的一条。
五、进阶：k 段就是把这个扫描叠 k 层
k = 2 的扫描只是第一层。一般情形的 DP：
def max_variance_sum(a, k):
n = len(a)
S1 = [0] * (n + 1)
S2 = [0] * (n + 1)
for i in range(1, n + 1):
S1[i] = S1[i - 1] + a[i - 1]
S2[i] = S2[i - 1] + a[i - 1] * a[i - 1]
def var(l, r): # 段 [l+1, r] 的总体方差，O(1)
length = r - l
if length <= 0:
return 0.0
s = S1[r] - S1[l]
q = S2[r] - S2[l]
return q / length - (s / length) * (s / length)
NEG = float('-inf')
dp = [[NEG] * (k + 1) for _ in range(n + 1)]
dp[0][0] = 0.0
for i in range(1, n + 1):
for j in range(1, min(i, k) + 1):
best = NEG
for m in range(j - 1, i):
if dp[m][j - 1] == NEG:
continue
cand = dp[m][j - 1] + var(m, i)
if cand > best:
best = cand
return dp[n][k] if k <= n else None
复杂度
O(n^2 k)。如果段长有下界、或者题目保证最优切点满足单调性，可以用分治 DP 或斜率优化把内层压掉；但
先写对 O(n^2 k)，再谈优化 —— 面试里写个错的高复杂度不如写个对的低复杂度。
如果题目问的是
最小化（更常见的工业形态：分箱、图像分割、K-均值式的代价函数），代码只改一个符号：
max 换
min，
NEG 换
INF。
六、Java 版
public class PartitionVariance {
// 切成恰好 k 段，使各段总体方差之和最大；k > n 时无解返回 null
public static Double maxVarianceSum(int[] a, int k) {
int n = a.length;
if (k > n) return null;
double[] s1 = new double[n + 1];
double[] s2 = new double[n + 1];
for (int i = 1; i <= n; i++) {
s1[i] = s1[i - 1] + a[i - 1];
s2[i] = s2[i - 1] + (double) a[i - 1] * a[i - 1];
}
// 段 [l, i) 的总体方差，O(1)
java.util.function.BiFunction<Integer, Integer, Double> var = (l, i) -> {
int len = i - l;
if (len <= 0) return 0.0;
double sum = s1[i] - s1[l];
double sq = s2[i] - s2[l];
double mean = sum / len;
return sq / len - mean * mean;
};
final double NEG = Double.NEGATIVE_INFINITY;
double[][] dp = new double[n + 1][k + 1];
for (double[] row : dp) java.util.Arrays.fill(row, NEG);
dp[0][0] = 0.0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= Math.min(i, k); j++) {
double best = NEG;
for (int m = j - 1; m < i; m++) {
if (dp[m][j - 1] == NEG) continue;
best = Math.max(best, dp[m][j - 1] + var.apply(m, i));
}
dp[i][j] = best;
}
}
return dp[n][k] == NEG ? null : dp[n][k];
}
}
注意
(double) a[i - 1] * a[i - 1] 里的强转：
int 自乘在值稍大时就溢出（
46341^2 就超过
int 上限），平方和必须落在
double 或
long 上。
七、边界情况
k = 1：答案就是全序列总体方差 —— 这是 DP 的第一层基例，也是「不切」的对照组。k = n：每段一个元素，方差全是 0，答案 0。k > n：无解（段数不能超过元素数），返回 null 而不是抛异常。- 全相等序列：任何切法合计都是 0。
- 含负数：公式不变（平方和非负、与符号无关），但
mean 可能为负，别在均值上写绝对值。
- 总体方差 vs 样本方差：本文全程用总体方差（除以长度
n）。若题目要样本方差（除以 n-1），单点段没有定义，k = n 会直接崩 —— 必须先和面试官对齐口径。
八、复杂度
贪心为什么不行：主例里切点 2 的左段方差 9.00 是全场最高，但切点 4 的左段方差 9.25 更高、合计反而更低（右段掉到 2.25）。局部最优的段方差和全局最优的合计没有单调关系，只有 DP 这种「枚举切点 + 查表」才保险。
九、常见坑
9.1 每切点重算方差，复杂度退化成 O(n^3)
不建前缀和、每个切点都
sum 一遍再算方差，
k = 2 就从
O(n) 变
O(n^2)，一般 k 变
O(n^3 k)。一阶/二阶前缀和各两行，是这道题性价比最高的优化。
9.2 口径混用：总体方差和样本方差
DP 的转移要求「段方差可加」—— 只有总体方差（各除各的长度）满足这个结构。混用
n-1 会让
k = n 除零，也会让不同段之间的数没法比。
动手前先问清楚口径。
9.3 以为切得越多方差和越小
主例用数字打脸：
k = 1 是 6.92，
k = 2 是 14.69。记住离差平方和分解：等长时最大化组内等价于最小化组间（让各段均值靠近），不是「切碎」。
9.4 int 溢出 / 浮点误差
平方和用
int 会在中等规模就溢出；用
double 时，
E[x^2] - E[x]^2 在数据量级极大且有微小方差时会出现
灾难性抵消（两个大数相减）。稳妥做法是先整体减去一个基准（比如均值）再平方，或者用
BigDecimal / Kahan 求和。
9.5 忘了单点段方差为 0
k = n 的答案是 0、
k > n 无解、以及 DP 里
range(j - 1, i) 的下界从
j - 1 起（保证每段至少一个元素）—— 三处都源于同一条：段不能为空。
9.6 把「最大」当成默认
工业场景（分箱、图像分割）通常问
最小化，因为那是「组内越齐越好」的代价函数。LeetCode / 面试题则常问最大来考验理解。
读题时把 max/min 圈出来，代码里只差一个词。
十、面试怎么答
- 先给 DP 式子："
dp[i][j] = max_{k} dp[k][j-1] + var(k+1..i)，k = 2 时就是扫一遍切点。"
- 再给 O(1) 方差公式："一阶二阶前缀和，
var = E[x^2] - E[x]^2，O(n^2 k) 总复杂度。"
- 主动说反直觉点："切成两段可以比不切更大 —— 主例 6.92 对 14.69，因为两段各自的均值把原本抵消的偏离放大了。"
- 提恒等式："离差平方和分解
SS_total = SS_within + SS_between；等长切分时最大化组内等价于最小化组间，段长不等时这条捷径不成立。"
- 报边界：
k = 1 全序列方差、k = n 答案 0、k > n 无解、单点段方差 0。
- 报变体：最小化版（改一个符号，工业上更常见）、段长下界（
m 从 j-1 改成 max(j-1, i-minLen)）、分治 DP / 斜率优化、以及它在 K-均值和图像分割里的位置。
结语
序列切分方差题的骨架很小：一个 DP 式子、一条前缀和公式。它真正考的是两件事 ——
你敢不敢相信反直觉的答案（切成两段方差和反而翻倍，因为各段均值把互相抵消的偏离单独放大了），以及
你愿不愿意把 O(1) 的段方差算清楚（
E[x^2] - E[x]^2 两行前缀和，换掉整个内层的
O(n)）。上一篇
石子游戏 的功夫在归约，这一篇的功夫在公式 —— DP 题的档次，往往就藏在这两条里。