1function largestSumOfAverages(nums, k) {
2    const n = nums.length;
3    const prefixSum = new Array(n + 1).fill(0);
4    const dp = Array.from({ length: n }, () => new Array(k).fill(0));
5
6    for (let i = 0; i < n; ++i) {
7        prefixSum[i + 1] = prefixSum[i] + nums[i];
8    }
9
10    for (let i = 0; i < n; ++i) {
11        dp[i][0] = (prefixSum[n] - prefixSum[i]) / (n - i);
12    }
13
14    for (let m = 1; m < k; ++m) {
15        for (let i = 0; i < n; ++i) {
16            for (let j = i + 1; j < n; ++j) {
17                dp[i][m] = Math.max(dp[i][m], (prefixSum[j] - prefixSum[i]) / (j - i) + dp[j][m - 1]);
18            }
19        }
20    }
21
22    return dp[0][k - 1];
23}
24
25const nums = [9, 1, 2, 3, 9];
26const k = 3;
27console.log(largestSumOfAverages(nums, k).toFixed(5));

1#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

const int MAX_N = 100;
double memo[MAX_N][MAX_N];
double prefix_sum[MAX_N + 1];

// Recursive function to find the best partitioning
// i: starting index, k: partitions left
static double solve(int i, int k, int n) {
    if (k == 1) return (prefix_sum[n] - prefix_sum[i]) / (n - i);
    if (memo[i][k] != -1) return memo[i][k];

    double maxScore = 0;
    for (int j = i + 1; j <= n - (k - 1); ++j) {
        maxScore = max(maxScore, (prefix_sum[j] - prefix_sum[i]) / (j - i) + solve(j, k - 1, n));
    }

    return memo[i][k] = maxScore;
}

int main() {
    vector<int> nums = {9, 1, 2, 3, 9};
    int k = 3;
    int n = nums.size();

    memset(memo, -1, sizeof(memo));
    prefix_sum[0] = 0;
    for (int i = 0; i < n; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + nums[i];
    }

    cout << fixed << setprecision(5) << solve(0, k, n) << endl;
    return 0;
}