Largest Sum of Averages

We partition a row of numbers A into at most K adjacent (non-empty) groups, then our score is the sum of the average of each group. What is the largest score we can achieve?

Note that our partition must use every number in A, and that scores are not necessarily integers.

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

Note:

• 1 <= A.length <= 100.

• 1 <= A[i] <= 10000.

• 1 <= K <= A.length.

• Answers within 10^-6 of the correct answer will be accepted as correct.

// Max SUM of averages will be acheived when we make max possible groups
// Than means making K groups or N groups if K>N
class Solution {
    public double largestSumOfAverages(int[] A, int K) {
        int N = A.length;
        double[][] dp = new double[N + 1][N + 1];
        // dp[i][j] -> Max sum of averages for first i elements
        // and making exactly j groups or N whichever is smaller
        double sum = 0;
        // base case when number of groups = 1
        for (int i = 0; i < N; ++i) {
            sum += A[i];
            dp[i + 1][1] = sum / (i + 1);
        }
        return search(N, K, A, dp);
    }

    public double search(int n, int k, int[] A, double[][] dp) {
        if (dp[n][k] > 0)
            return dp[n][k];
        // if N < k then answer is not possible
        // we want k<=N
        if (n < k)
            return 0;
        double sum = 0;
        // trying different groups from n -> i
        // with average = sum(n->i)/(n-i)
        // because this group will contain n-i elements
        for (int i = n - 1; i > 0; --i) {
            sum += A[i];
            // Recurring for the rest of the smaller part (1 -> i)
            // the remaining part will form k-1 groups and return their highest sum
            dp[n][k] = Math.max(dp[n][k], search(i, k - 1, A, dp) + sum / (n - i));
        }
        return dp[n][k];
    }
}