给定数组 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
动态规划
class Solution {
public:double largestSumOfAverages(vector<int>& nums, int k) {int n = nums.size();vector<double> pre(n+1);for(int i = 0; i < n; i++){pre[i+1] = pre[i] + nums[i];}vector<vector<double>> f(n+1, vector<double>(n+1));for(int i = 1; i <= n; i++){f[i][1] = pre[i] / i;}for(int j = 2; j <= k; j++){for(int i = j; i <= n; i++){for(int x = j-1; x < i; x++){f[i][j] = max(f[i][j], f[x][j-1] + (pre[i] - pre[x]) / (i-x));}}}return f[n][k];}
};
时间复杂度：O(N^3)
空间复杂度：O(N^2)
首先我们定义一个二维数组f[i][j]，含义是前i个元素分割成j个，能分割成的最大平均值和。那么我们就可以知道状态转换方程，f[i][j] = max(f[i][j], f[x][j-1] + (pre[i] - pre[x]) / (i-x));，也就是说，我们枚举i后，从j-1到i-1的范围内枚举x，这样子f[i][j]就可以由f[x][j-1]加上第x个元素到第i个元素的平均值转移而来。
那么第x个元素到第i个元素的平均值就需要使用前缀和来计算，这样子可以加快效率。我们定义pre来记录前缀和。
最后我们返回f[n][k]即可。
空间优化
class Solution {
public:double largestSumOfAverages(vector<int>& nums, int k) {int n = nums.size();vector<double> pre(n+1);for(int i = 0; i < n; i++){pre[i+1] = pre[i] + nums[i];}vector<double> f(n+1);for(int i = 1; i <= n; i++){f[i] = pre[i] / i;}for(int j = 2; j <= k; j++){for(int i = n; i >= 0; i--){for(int x = j-1; x < i; x++){f[i] = max(f[i], f[x] + (pre[i] - pre[x]) / (i-x));}}}return f[n];}
};
时间复杂度：O(k×n^2)
空间复杂度：O(n)
在状态转移方程中，我们可以注意到我们只需要f[x][j-1],也就是j-1来转换。那么我们就可以使用空间压缩的办法，但是需要注意的是，我们的i需要倒序。为什么i不能正序呢？因为由于我们状态进行了压缩，所以f[x]里面实际上保存的信息是上一轮的数据，如果我们i使用正序去遍历，那么f[i]就会覆盖掉f[x]的数据，导致在状态转移的过程中，无法读取到上一轮的f[x]的数据。
