1#include <stdio.h>
2#include <string.h>
3#include <math.h>
4
5#define MAX_N 100
6
7double largestSumOfAverages(int* nums, int numsSize, int k) {
8    double prefix_sum[MAX_N + 1];
9    double dp[MAX_N][MAX_N];
10    memset(dp, 0, sizeof(dp));
11    
12    // Calculate prefix sums
13    prefix_sum[0] = 0;
14    for (int i = 0; i < numsSize; ++i) {
15        prefix_sum[i + 1] = prefix_sum[i] + nums[i];
16    }
17    
18    // Base case for one partition
19    for (int i = 0; i < numsSize; ++i) {
20        dp[i][0] = (prefix_sum[numsSize] - prefix_sum[i]) / (numsSize - i);
21    }
22    
23    // Fill dp for up to k partitions
24    for (int m = 1; m < k; ++m) {
25        for (int i = 0; i < numsSize; ++i) {
26            for (int j = i + 1; j < numsSize; ++j) {
27                dp[i][m] = fmax(dp[i][m], (prefix_sum[j] - prefix_sum[i]) / (j - i) + dp[j][m - 1]);
28            }
29        }
30    }
31    
32    return dp[0][k - 1];
33}
34
35int main() {
36    int nums[] = {9, 1, 2, 3, 9};
37    int numsSize = 5;
38    int k = 3;
39    printf("%.5f\n", largestSumOfAverages(nums, numsSize, k));
40    return 0;
41}

1#include <iostream>
#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;
}