Largest Sum of Averages

Problem Statement

In this problem, you are provided with an integer array nums and an integer k. Your task is to split the array into at most k contiguous subarrays in such a manner that maximizes the combined score of the partitions. The score of a particular partitioning is calculated by summing up the averages of each subarray formed. It's required that all elements from the original array must be utilized in creating these subarrays. The maximum achievable score is a floating-point number, and you are required to return this maximum score with a precision that is close to the actual maximum score within 10^-6.

Examples

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

Constraints

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 104
• 1 <= k <= nums.length

Approach and Intuition

The task involves analyzing and calculating the maximum score from arbitrary partitions, which means we need to find an optimal way to divide the array into parts such that their averages contribute to a maximum sum.

1. Dynamic Programming Strategy:

   • We can use dynamic programming to solve this task efficiently. We'll denote dp[i][j] as the maximum score achievable using the first i items of nums divided into j partitions.

2. Generate all possible partition configurations:

   • Iterate through each element and each possible partition count, evaluating and storing the maximum cumulative score that can be obtained if the current element is considered as the end of a partition.

3. Utilizing Cumulative Sums for Efficient Average Calculation:

   • Use an auxiliary array to hold cumulative sums which allows for quick calculation of sum for subarrays, consequently deriving averages swiftly when required.

4. Choosing the Optimal Partitions with Recursive Division:

   • For each possible ending point of a subarray within the allowed partitions, recursively determine which division would yield a maximum score by either including the current element in the existing subarray or starting a new subarray with it.

5. Base and Initialization Cases:

   • If there's only one partition allowed (i.e., k=1), the whole array is one subarray, and its average is its score.
   • If every element needs to be its partition (i.e., when k is equal to the array length), then the score is simply the sum of all elements as each will solely form a subarray.

This approach ensures that instead of bruteforcing through all possible partition mechanisms, we systematically build on smaller solutions, making it more computationally efficient given the constraints, and leading to the derivations of maximum possible scores within the desired precision.

Solutions

class Solution {
    public double maxAverageSum(int[] nums, int groups) {
        int len = nums.length;
        double[] prefixSum = new double[len+1];
        for (int i = 0; i < len; ++i) {
            prefixSum[i+1] = prefixSum[i] + nums[i];
        }

        double[] curr = new double[len];
        for (int i = 0; i < len; ++i) {
            curr[i] = (prefixSum[len] - prefixSum[i]) / (len - i);
        }

        for (int k = 0; k < groups-1; ++k) {
            for (int i = 0; i < len; ++i) {
                for (int j = i+1; j < len; ++j) {
                    curr[i] = Math.max(curr[i], (prefixSum[j]-prefixSum[i]) / (j-i) + curr[j]);
                }
            }
        }

        return curr[0];
    }
}