最大平均值和的分组

记住这套:前缀和算区间平均,dp[i][k] 枚举「第一组切到哪」再加上后面少一组的结果。题面是「最多 k 组」,但本题 nums 是正数,多切一组分数只升不降,最优一定用满 min(k,n)=3 组,所以下面直接按「恰好分 k 组」的 dp[i][k] 来做。

先看原始数据:[9,1,2,3,9]。直觉上两头的 9 自己单独成组最划算,中间的小数挤在一起摊平均。这个直觉待会儿用 DP 来证实。

把整条数组从左往右累加一遍,得到前缀和数组 s。s[0] 规定为 0,s[1]=9,s[2]=10,一直到 s[5]=24。有了它,任何一段的和都能一减就出来。

换成前缀和数组看一眼。想求中间 [1,2,3] 这一段的和,直接 s[4] 减 s[1] 等于 6;长度是 3,平均就是 2。不用每次重新加一遍,这就是前缀和省下的功夫。

再算个整段做对照:全部 5 个数塞进一组,和是 24,平均 4.8。这就是 k=1 时的分数,显然太低。下面正式开填 dp 表,看分多组能拉到多高。

搭一张表:行是起点 i(从第几个数开始),列是还能分几组 k。右下角灰掉的「无」是元素不够分那么多组的格子,比如最后一个数没法分成 2 组。正数下多切一组分数不降,最优会用满 min(k,n)=3 组,所以这里直接按 exact-k 的 dp[i][k] 填。我们从最左一列 k=1 往右填。

先填最简单的 k=1 列。只剩一组,意味着从 i 到末尾整段不能再切,分数就是这一整段的平均值。一格一格来。

从最底下 i=4 开始:只剩一个数 9,自己成一组,平均就是 9。填进 dp[4][1]。

i=3:剩下 [3,9] 两个数挤一组,和 12、平均 6。填 dp[3][1]=6。

i=2:剩 [2,3,9] 三个数一组,和 14、平均约 4.67。可以看到一整段塞一起,平均被小数拖下来了。

i=1:剩 [1,2,3,9] 四个数一组,和 15、平均 3.75。

i=0:全部 5 个数一组,平均 4.8。k=1 这一列填满了。这些就是「后面只许一组」时各起点的最优,后面分多组要靠它们当地基。

进入 k=2 列。现在允许切两组:枚举第一组在哪结束,前半段取平均,后半段就是已经算好的 dp[j][1]。注意 i=4 只有一个数,分不出两组,标「无」。

i=3:剩 [3,9],分两组只有一种切法,第一组 [3]、第二组 [9]。3 加 9 等于 12,比挤一组的 6 整整高了一倍。填 dp[3][2]=12。

i=2:剩 [2,3,9],两个切点可选。切在 [2] 之后是 2 加 6 等于 8;切在 [2,3] 之后是 2.5 加 9 等于 11.5。取大的 11.5,这意味着把 9 单独留出来更值。

i=1:剩 [1,2,3,9],三个切点都试。切完 [1] 是 1 加 4.67;切完 [1,2] 是 1.5 加 6;切完 [1,2,3] 是 2 加 9 等于 11,最大。又是把末尾的 9 单独拎出来赢了。dp[1][2]=11。

i=0 全段分两组,四个切点逐一算:把开头的 9 单独切出来得 12.75;把末尾的 9 单独切出来也是 12.75。两个并列最高,中间那些切法都差一截。

取最大值 12.75 填进 dp[0][2]。两个并列时代码取先遇到的,也就是切点 j=1、第一组是开头那个 9。k=2 列填满了。

最后一列 k=3。转移一模一样,只是这次后半段接的是 k=2 那一列的结果。i=3、i=4 元素不够分三组,标「无」。我们要的答案 dp[0][3] 就在这一列最上面。

i=2:剩 [2,3,9] 分三组,只能每个数各成一组,2 加 3 加 9 等于 14。换个角度:第一组切 [2],后面 [3,9] 正好是刚才算好的 dp[3][2]=12,2 加 12 也是 14,对得上。

i=1:剩 [1,2,3,9] 分三组。切完 [1] 接 dp[2][2]=11.5 得 12.5;切完 [1,2] 接 dp[3][2]=12 得 13.5,更大。dp[1][3]=13.5。

到正主了:i=0 全段分三组。把开头 9 单独切出来,后面 [1,2,3,9] 分两组正好是 dp[1][2]=11,9 加 11 等于 20!其它切法都到不了 20。

取最大值 20 填进 dp[0][3]。这就是「从头开始、最多分三组」的最优分数,也就是题目要的答案。整张表填完了。

顺着每格当初选的切点回溯一遍:dp[0][3] 选了第一组 [9],跳到 dp[1][2];dp[1][2] 选了第一组 [1,2,3],跳到 dp[4][1];最后 [9] 收尾。三组就是 [9]、[1,2,3]、[9]。

回到原数组看最终分法:绿色 [9] 一组、蓝色 [1,2,3] 一组、红色 [9] 一组。9 加 2 加 9 等于 20,和 dp 表算出的答案严丝合缝。两头的大数各自独占一组,中间小数摊平,这正是最优。

边界先想清:k=1 就是整段平均;k 等于长度时每个数各成一组、答案是所有数之和;单个数直接返回它自己。

面试重点:讲清最优子结构(切点牵一发动全身)和正数特例(分越多越好)的边界。