Untitled

import java.util.Arrays;

public class PartitionMaxAverageRecursive {
    public double maxScore(int[] nums, int k) {
        int n = nums.length;
        // Prefix sum array to calculate subarray sums quickly
        double[] prefixSum = new double[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        // Memoization table
        double[][] memo = new double[n][k + 1];
        for (double[] row : memo) {
            Arrays.fill(row, -1.0); // Initialize with an invalid state
        }

        // Start the recursion
        return dfs(nums, prefixSum, n, k, 0, memo);
    }

    private double dfs(int[] nums, double[] prefixSum, int n, int k, int index, double[][] memo) {
        // Base case: If no partitions left and we've used all elements
        if (k == 0) {
            return index == n ? 0 : Double.NEGATIVE_INFINITY; // Invalid if not all elements are used
        }

        // Base case: If we've reached the end but still have partitions left
        if (index == n) {
            return Double.NEGATIVE_INFINITY; // Impossible to partition
        }

        // If already computed, return the value
        if (memo[index][k] != -1.0) {
            return memo[index][k];
        }

        double maxScore = Double.NEGATIVE_INFINITY;

        // Try to partition at every possible point
        for (int i = index; i <= n - k; i++) {
            double currentAvg = (prefixSum[i + 1] - prefixSum[index]) / (i - index + 1);
            maxScore = Math.max(maxScore, currentAvg + dfs(nums, prefixSum, n, k - 1, i + 1, memo));
        }

        // Store the result in memo and return
        memo[index][k] = maxScore;
        return maxScore;
    }

    public static void main(String[] args) {
        PartitionMaxAverageRecursive solution = new PartitionMaxAverageRecursive();

        int[] nums1 = {9, 1, 2, 3, 9};
        int k1 = 3;
        System.out.printf("%.5f\n", solution.maxScore(nums1, k1)); // Output: 20.00000

        int[] nums2 = {1, 2, 3, 4, 5, 6, 7};
        int k2 = 4;
        System.out.printf("%.5f\n", solution.maxScore(nums2, k2)); // Output: 20.50000
    }
}