教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载导读本篇以「宫水三叶的刷题日记」系列仓库LogicStack-LeetCode中 813. 最大平均值和的分组中等 的官方题解为骨架完整讲解「序列 DP 前缀和」这一经典组合套路如何将把数组切成最多 m 段、最大化各段平均值之和的优化问题转化为可递推的动态规划模型并给出 Java、C、Python、TypeScript 四种可直接提交的完整实现。读完本文你将掌握连续段划分类 DP 的通用状态定义方法、用前缀和将区间求和压到 O(1) 的优化手段以及划分越多平均值之和越大这一关键数学结论并能举一反三地迁移到同仓库 序列 DP 专题 与 前缀和专题 中的一系列题目。题目描述这是 LeetCode 上的813. 最大平均值和的分组Largest Sum of Averages难度为中等。Tag序列 DP、前缀和、动态规划、数学给定数组nums和一个整数m。我们将给定的数组nums分成最多m个相邻的非空子数组分数由每个子数组内的平均值的总和构成。注意必须使用nums数组中的每一个数进行分组并且分数不一定需要是整数。返回我们所能得到的最大分数是多少。答案误差在 $10^{-6}$ 内被视为是正确的。示例 1输入: nums [9,1,2,3,9], m 3 输出: 20.00000 解释: nums 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 (1 2 3) / 3 9 20. 我们也可以把 nums 分成[9, 1], [2], [3, 9]. 这样的分组得到的分数为 5 2 6 13, 但不是最大值.示例 2输入: nums [1,2,3,4,5,6,7], m 4 输出: 20.50000提示$1 \le nums.length \le 100$$1 \le nums[i] \le 10^4$$1 \le m \le nums.length$问题转化从最多 m 段到恰好 m 段先抓住题目的本质约束相邻、非空、必须覆盖全部元素。题意可以整理为一句话将 $n$ 个元素划分为「最多」$m$ 个连续段最大化连续段的平均值之和。这里的关键难点有两个连续段划分数量不定是最多 m 段而不是恰好 m 段目标函数是非线性的平均值之和段与段之间的平均值不能直接相加求和化简必须逐段计算。对于第一个难点原题解给出了一条简洁的数学结论来简化问题划分份数越多平均值之和越大因此想要取得最大值必然是恰好划分成 $m$ 份。直觉上可以这样理解把一段拆成两个非空子段后新分数的变化等价于把原先的整体平均值替换为两个子段平均值的加权组合而拆分会暴露出段内高值元素对平均值的贡献整体不会更差。因此最优解一定落在用满 $m$ 段这一极端情形上$f[n][m]$ 即为最终答案无需对 $1 \le k \le m$ 逐一取最大值。这一结论在原文档中被明确给出是本题能否从最多简化为恰好的关键一步属于典型的数学 DP复合题型同仓库 数学专题 中亦有大量此类思路。状态定义序列 DP 的核心骨架采用序列 DP 的标准套路。为了方便令所有数组下标从 $1$ 开始前缀和数组与 DP 数组统一使用 $n 10$、$m 10$ 的裕量尺寸规避边界判断。定义$f[i][j]$ 为考虑将前 $i$ 个元素划分成 $j$ 份的最大平均和。那么答案就是 $f[n][k]$其中 $1 \le k \le m$根据上文结论取 $k m$ 即可。这一状态定义与同仓库 序列 DP 专题 中的同类题目保持一致f[i][j]的前缀长度 段数双维度刻画是连续段划分问题最通用的建模方式。例如 689. 三个无重叠子数组的最大和 同样使用前 i 个数凑 j 个无重叠子数组的状态定义只是转移时固定了段长 $k$。状态转移按 j 的大小分情况讨论由于划分出来的子数组不能是空集因此可以根据 $j$ 的大小分情况讨论 $f[i][j]$ 的计算情形一$j 1$整个前缀作为一段此时前 $i$ 个元素只能整体划成一段平均值就是前缀平均值$$ f[i][j] \frac{\sum_{idx 1}^{i} nums[idx - 1]}{i} $$情形二$j 1$枚举最后一个子数组的起点枚举最后一个子数组的起点 $k$其中 $2 \le k \le i$。此时前 $k - 1$ 个元素被划分成 $j - 1$ 段最优值为 $f[k - 1][j - 1]$而 $[k, i]$ 作为第 $j$ 段其平均值为 $\frac{\sum_{idx k}^{i} nums[idx]}{i - k 1}$。于是$$ f[i][j] \max_{2 \le k \le i}\left(f[k - 1][j - 1] \frac{\sum_{idx k}^{i} nums[idx]}{i - k 1}\right) $$最终 $f[i][j]$ 为枚举所有 $k$ 值所得结果的最大值。注意 $k$ 从 $2$ 开始枚举的原因$j 1$ 时前 $k - 1$ 个元素至少要能容纳 $j - 1$ 个非空段即 $k - 1 \ge j - 1$而最紧的情形就是 $k 2$同时这样也天然保证了最后一个子数组非空$i - k 1 \ge 1$。前缀和优化把区间求和压到 O(1)转移方程中的 $\sum_{idx k}^{i} nums[idx]$ 是一个连续区间求和若每次枚举都现场累加会让总复杂度多出一个 $O(n)$ 因子。用一维前缀和预处理即可$$ sum[i] sum[i - 1] nums[i - 1] $$则区间 $[k, i]$ 的和为 $sum[i] - sum[k - 1]$。于是转移式改写为$$ f[i][j] \max_{2 \le k \le i}\left(f[k - 1][j - 1] \frac{sum[i] - sum[k - 1]}{i - k 1}\right) $$同样的前缀和加速连续段求和手段在 前缀和专题 中被广泛使用例如 689. 三个无重叠子数组的最大和 用sum[i k - 1] - sum[i - 1]求长度为 $k$ 的窗口和2304. 网格中的最小路径代价 则将其扩展到二维场景。前缀和 DP 的组合在本仓库中是一对高度默契的搭档。完整可提交代码四种语言原文档为方便读者在本地调试与直接提交给出了 Java、C、Python、TypeScript 四种等价实现。以下代码均以下标从 $1$ 开始、数组开 $n 10$ / $m 10$ 裕量空间的方式实现逻辑完全一致。Java 代码class Solution { public double largestSumOfAverages(int[] nums, int m) { int n nums.length; double[] sum new double[n 10]; for (int i 1; i n; i) sum[i] sum[i - 1] nums[i - 1]; double[][] f new double[n 10][m 10]; for (int i 1; i n; i) { for (int j 1; j Math.min(i, m); j) { if (j 1) { f[i][1] sum[i] / i; } else { for (int k 2; k i; k) { f[i][j] Math.max(f[i][j], f[k - 1][j - 1] (sum[i] - sum[k - 1]) / (i - k 1)); } } } } return f[n][m]; } }C 代码class Solution { public: double largestSumOfAverages(vectorint nums, int m) { int n nums.size(); vectordouble sum(n 10, 0); for (int i 1; i n; i) sum[i] sum[i - 1] nums[i - 1]; vectorvectordouble f(n 10, vectordouble(m 10, 0)); for (int i 1; i n; i) { for (int j 1; j min(i, m); j) { if (j 1) { f[i][j] sum[i] / i; } else { for (int k 2; k i; k) { f[i][j] max(f[i][j], f[k - 1][j - 1] (sum[i] - sum[k - 1]) / (i - k 1)); } } } } return f[n][m]; } };Python 代码class Solution: def largestSumOfAverages(self, nums: List[int], m: int) - float: n len(nums) psum [0] * (n 10) for i in range(1, n 1): psum[i] psum[i - 1] nums[i - 1] f [[0] * (m 10) for _ in range(n 10)] for i in range(1, n 1): for j in range(1, min(i, m) 1): if j 1: f[i][j] psum[i] / i else: for k in range(2, i 1): f[i][j] max(f[i][j], f[k - 1][j - 1] (psum[i] - psum[k - 1]) / (i - k 1)) return f[n][m]TypeScript 代码function largestSumOfAverages(nums: number[], m: number): number { const n nums.length const sum new Arraynumber(n 10).fill(0) for (let i 1; i n; i) sum[i] sum[i - 1] nums[i - 1] const f new ArrayArraynumber() for (let i 0; i n 10; i) f[i] new Arraynumber(m 10).fill(0) for (let i 1; i n; i) { for (let j 1; j Math.min(i, m); j) { if (j 1) { f[i][j] sum[i] / i } else { for (let k 2; k i; k) { f[i][j] Math.max(f[i][j], f[k - 1][j - 1] (sum[i] - sum[k - 1]) / (i - k 1)) } } } } return f[n][m] }实现细节要点j 的枚举上界取Math.min(i, m)前 $i$ 个元素最多只能分成 $i$ 个非空段同时不超过题目给定的 $m$两者取小即可剪掉大量无效状态j 1 单独处理这是递推的基态避免出现 $f[0][0]$ 之类的空段定义歧义内层 k 从 2 枚举到 i确保前 $k - 1$ 个元素至少能容纳 $j - 1$ 个非空段同时最后一个段非空全程使用浮点数运算题目明确分数不一定需要是整数因此sum与f数组都用double/ 浮点类型承载。复杂度分析时间复杂度$O(n^2 \times m)$。三重循环分别枚举 $i$$O(n)$、$j$$O(m)$、$k$$O(n)$且 $j$ 的上界被min(i, m)约束最坏情况下为 $O(n^2 m)$。在 $n \le 100$ 的数据规模下完全可行。空间复杂度$O(n \times m)$。$f$ 数组为 $(n 10) \times (m 10)$ 的二维表$sum$ 数组为 $O(n)$总空间为 $O(nm)$。用示例验证转移过程以示例 1nums [9,1,2,3,9]$m 3$$n 5$为例走一遍核心结论最优分组为[9]、[1,2,3]、[9]分数 $ 9 (123)/3 9 20.00000$对应 $f[5][3]$次优分组[9,1]、[2]、[3,9]的分数为 $5 2 6 13$不是最大值。对比可见把[1,2,3]单独成段后其平均值 2 大于把[9,1]绑在一起得到的 5 与后续组合的整体贡献这正是枚举最后一个段起点 $k$ 并取max的原因——DP 会尝试所有切分点保证 $f[5][3]$ 一定收敛到 20。横向扩展同一套路的仓库内姊妹题序列 DP 前缀和是一套可以反复套用的组合技在 LogicStack-LeetCode 仓库的 序列 DP 专题 与 前缀和专题 中都能找到大量变体推荐按以下顺序练习三个无重叠子数组的最大和困难同样是前 i 个数凑 j 段的状态定义但段长固定为 $k$并额外考察了回溯输出字典序最小方案的能力单词拆分中等前缀匹配问题可借助前缀思想与 DP 判断是否可由字典词拼接规划兼职工作困难区间调度 序列 DP 的进阶应用最长公共子序列中等最经典的二维序列 DP用于夯实f[i][j]双维度建模的基本功一维数组的动态和简单前缀和最入门的直球应用适合先巩固前缀和本身。小结813 题是序列 DP 前缀和 数学结论三者结合的典型中等题解题链条可以浓缩为四步化归利用划分越多平均值之和越大的数学结论把最多 m 段收紧为恰好 m 段建模定义 $f[i][j]$ 为前 $i$ 个元素划成 $j$ 段的最大平均和答案取 $f[n][m]$转移按 $j 1$ 与 $j 1$ 分情况$j 1$ 时枚举最后一个段的起点 $k$ 取最大值优化用一维前缀和 $sum$ 把连续段求和降为 $O(1)$总复杂度 $O(n^2 m)$。掌握这套前缀长度 段数的状态定义与枚举最后一段起点的转移模式后面对任何连续段划分优化类题目都可以快速照搬骨架。完整题解与系列文章收录于本仓库 813. 最大平均值和的分组中等仓库说明见 README.md更多按 Tag 分类的题目清单可查阅 Index 目录 下各专题索引。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LogicStack-LeetCode 题解LeetCode 1749 任意子数组和的绝对值的最大值——前缀和求区间和绝对值极值的 O(n) 解法LogicStack LeetCode 题解LeetCode 1749 任意子数组和的绝对值的最大值——前缀和求区间和绝对值极值的 O n 解法 本篇技术指南教程文档LeetCode 1537 最大得分题解双有序数组切换路径最大和的「前缀和分段构造」与「序列 DP」双解法LogicStack-LeetCode 刷穿系列LeetCode 1537 最大得分题解双有序数组切换路径最大和的「前缀和分段构造」与「序列 DP」双解法LogicStack LeetCode 刷穿系列教程文档diagrams 3 步生成自定义架构图Custom 节点本地/远程图标全解diagrams 3 步生成自定义架构图Custom 节点本地/远程图标全解 diagrams 是一个用 Python 代码表达云架构的开源库内置图标只覆盖数据可视化开发工具文档上一篇终极Daytona进程控制指南代码执行与结果获取API详解下一篇30分钟搞定FastAPI静态资源与API部署全流程从零到生产的终极指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考