class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<double> sum(n+10,0);
        for(int i=1;i<=n;i++)
        sum[i] = sum[i-1] + nums[i-1];
        vector<vector<double>> f(n+10,vector<double>(k+10,0));

        for(int i=1;i <= n;i++)
        {
            for(int j=1;j <=min(i,k);j++)
            {
                if(j == 1)
                {
                    f[i][1] = sum[i] / i;
                }
                else
                {
                    for(int ki=2;ki<=i;ki++)
                    {
                        f[i][j] = max(f[i][j], f[ki - 1][j - 1] + 
                        (sum[i] - sum[ki - 1]) / (i - ki + 1));
                    }
                }
            }
        }

        return f[n][k];
    }
};