You are given an integer array nums and an integer k. You can partition the array into at most k non-empty adjacent subarrays. The score of a partition is the sum of the averages of each subarray.

Note that the partition must use every integer in nums, and that the score is not necessarily an integer.

Return the maximum score you can achieve of all the possible partitions. Answers within 10-6 of the actual answer will be accepted.

&nbsp;
Example 1:

Input: nums = [9,1,2,3,9], k = 3
Output: 20.00000
Explanation: 
The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned nums into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.


Example 2:

Input: nums = [1,2,3,4,5,6,7], k = 4
Output: 20.50000


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 100
	1 &lt;= nums[i] &lt;= 104
	1 &lt;= k &lt;= nums.length


class Solution:
    def largestSumOfAverages(self, A, k):
        n = len(A)
        dp = [0] * n
        sum = 0
        for i in range(n-1,-1,-1):
            sum += A[i]
            dp[i] = sum / (n-i)
        for l in range(1,k):
            for i in range(n-l):
                sum = 0
                for j in range(i,n-l):
                    sum += A[j]
                    dp[i] = max(dp[i],dp[j+1] + sum / (j-i+1))
        return dp[0]
class Solution {
    Double dp[][][];
    int n;
    int k1;
    public double check(int b, int c,long sum,int n1,int ar[]){
        System.out.println(b+" "+c);
        if(dp[b][c][n1]!=null)
            return dp[b][c][n1];
        if(b==n){
            if(sum!=0)
            return (double)sum/(double)n1;
            else
                return 0.0;}
        if(c<k1&&sum>0)
            dp[b][c][n1]=Math.max((double)sum/(double)n1+check(b,c+1,0,0,ar),check(b+1,c,sum+(long)ar[b],n1+1,ar));
        else
            dp[b][c][n1]=check(b+1,c,sum+(long)ar[b],n1+1,ar);

        return dp[b][c][n1];
    }
    public double largestSumOfAverages(int[] nums, int k) {
        n=nums.length;
        k1=k-1;
        dp= new Double[n+1][k][n+1];
        return check(0,0,0l,0,nums);
    }
}
class Solution {
public:
    double solve(vector<int>&nums, int index, int k, vector<vector<double>>&dp){
        if(index<0)
            return 0;
        if(k<=0)
            return -1e8;

        if(dp[index][k]!=-1)
            return dp[index][k];

        double s_sum = 0;
        double maxi = INT_MIN;
        int cnt = 1;
        for(int i=index;i>=0;i--){
            s_sum += nums[i];
            maxi = max(maxi, (s_sum/cnt) + solve(nums, i-1, k-1, dp));
            cnt++;
        }
        return dp[index][k] = maxi;
    }

    double largestSumOfAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<double>>dp(n, vector<double>(k+1, -1));
        return solve(nums, n-1, k, dp);
    }
};
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var largestSumOfAverages = function(nums, k) {
    // set length
    const len = nums.length;
    // set sum by len fill
    const sum = new Array(len).fill(0);
    // set nums first to first of sum
    sum[0] = nums[0];

    // set every item of sum to the sum of the previous and the corresponding item of nums
    for (let i = 1; i < len; i++) {
        sum[i] = sum[i - 1] + nums[i];
    }

    // set dynamic programming
    const dp = new Array(k + 1).fill("").map(() => new Array(len).fill(0));

    // according to the meaning of the problem, set the value of dp
    for (let i = 0; i < len; i++) {
        dp[1][i] = sum[i] / (i + 1);
    }
    for (let i = 1; i <= k; i++) {
        dp[i][i - 1] = sum[i - 1];
    }
    for (let i = 2; i <= k; i++) {
        for (let j = i; j < len; j++) {
            for (let m = j - 1; m >= i - 2; m--) {
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][m] + (sum[j] - sum[m]) / (j - m));
            }
        }
    }

    // result
    return dp[k][len - 1];
};
Largest Sum of Averages