本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
C++动态规划
贪心(决策包容性)
LeetCode813. 最大平均值和的分组
给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 k 个非空子数组，且数组内部是连续的 。 分数 由每个子数组内的平均值的总和构成。
注意我们必须使用 nums 数组中的每一个数进行分组，并且分数不一定需要是整数。
返回我们所能得到的最大 分数 是多少。答案误差在 10-6 内被视为是正确的。
示例 1:
输入: nums = [9,1,2,3,9], k = 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], k = 4
输出: 20.50000
提示:
1 <= nums.length <= 100
1 <= nums[i] <= 104
1 <= k <= nums.length
动态规划+前缀和分解
令 n = nums.length
贪心
所有元素都会被选择，否则将未选择的元素加到邻近的组，结果一定变大。
一定分成了k组。如果少于k组，选择包括2个元素的组，拆分之，结果更大。
动态规划的状态表示
dp[i][k] 表示将nums前i个元素分成k组的最大平均和。空间复杂度：O(nk)
动态规划的状态方程
maxSelf(&dp[j][k+1],dp[i][k]+ nums[i…j-1]/(j-i))
枚举前置状态，对于每个前置状态i，i < j < n 。单个状态时间复杂度：O(n)
总时间复杂度：O(nkn)
动态规划的初始状态
dp[0][0]为0，其余为-1e9。
动态规划的填表顺序
i,k,j 从小到大。
动态规划的返回值
dp.back().back()
代码
核心代码
class Solution {public:double largestSumOfAverages(vector<int>& nums, const int K) {const int N = nums.size();vector<int> preSum(1);for (const auto& n : nums) {preSum.emplace_back(n + preSum.back());}vector<vector<double>> dp(N + 1, vector<double>(K+1,-1e9));dp[0][0] = 0;for (int i = 0; i < N; i++) {for (int k = 0; k < K; k++) {for (int j = i + 1; j <= N; j++) {dp[j][k + 1] = max(dp[j][k + 1],dp[i][k] + ((double)preSum[j]- preSum[i])/(j-i));}}}return dp.back().back();}};
单元测试
vector<int> nums;int k;TEST_METHOD(TestMethod11){nums = { 9, 1, 2, 3, 9 }, k = 3;auto res = Solution().largestSumOfAverages(nums, k);AssertEx(20.0, res);}TEST_METHOD(TestMethod12){nums = { 1,2,3,4,5,6,7 }, k = 4;auto res = Solution().largestSumOfAverages(nums, k);AssertEx(20.5, res);}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
