1import java.util.*;
2
3public class LargestSumOfAverages {
4    public double largestSumOfAverages(int[] nums, int k) {
5        int n = nums.length;
6        double[] prefix_sum = new double[n + 1];
7        double[][] dp = new double[n][k];
8
9        for (int i = 0; i < n; ++i) {
10            prefix_sum[i + 1] = prefix_sum[i] + nums[i];
11        }
12
13        for (int i = 0; i < n; ++i) {
14            dp[i][0] = (prefix_sum[n] - prefix_sum[i]) / (n - i);
15        }
16
17        for (int m = 1; m < k; ++m) {
18            for (int i = 0; i < n; ++i) {
19                for (int j = i + 1; j < n; ++j) {
20                    dp[i][m] = Math.max(dp[i][m], (prefix_sum[j] - prefix_sum[i]) / (j - i) + dp[j][m - 1]);
21                }
22            }
23        }
24
25        return dp[0][k - 1];
26    }
27
28    public static void main(String[] args) {
29        LargestSumOfAverages solution = new LargestSumOfAverages();
30        int[] nums = {9, 1, 2, 3, 9};
31        int k = 3;
32        System.out.printf("%.5f\n", solution.largestSumOfAverages(nums, k));
33    }
34}

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;
}