Leetcode 813. Largest Sum of Averages

Problem Explanation:

The problem asks to partition a list of integers into a maximum of k adjacent groups such that the sum of the averages of each group is maximized.

Approach to the solution:

The problem can be solved using dynamic programming. We maintain a dp table where dp[i][k] stores the maximum sum of averages we can get by partitioning the first i elements into k groups.

We start by calculating the prefix sum for the given list, which will help in calculating the average of a group in constant time using the formula (prefix[i] - prefix[j])/(i-j) for a group spaning from index j+1 to i.

Next, we iterate over the list and for each index i and for each group count k, we try to divide the list into k groups ending at index i. We do this by trying all possible last group positions and calculate the average of the last group and adding it to the maximum sum of averages we can get by dividing the rest of the list into k-1 groups. We store the maximum value obtained in dp[i][k}.

Finally the value stored in dp[n][K] gives the answer, where n is the length of the list.

Walk through an example:

We have the list of numbers as [9,1,2,3,9] and K = 3.

The prefix sum will be calculated as [9, 10, 12, 15, 24]

Now Iterating for k = 1 to 3, for k = 1, Since there could only be 1 group, the average will be the sum of the elements till index i divided by the number of elements which also is the prefix sum till that index divided by the number of elements. So

1
2
3dp[1][1] = 9.0/1 = 9.0
4dp[2][1] = 10.0/2 = 5.0
5dp[3][1] = 12.0/3 = 4.0
6dp[4][1] = 15.0/4 = 3.75
7dp[5][1] = 24.0/5 = 4.8

Next for k = 2, we iterate for 1 < i < 5, For i = 2, the second group will contain the elements at index 1 and dp[1][1] will form the first group. Similarly for i = 3, the second group can either have the element at index 2 or elements at index 2 and 3. So we update dp[3][2] with the maximum sum. We can get the average by subtracting the prefix sum till end of the first group with the prefix sum till end of the second group and divide it by the number of elements in the second group, which is end of the second group - end of the first group. Similarly we will update dp[4][2] and dp[5][2]

1
2
3dp[2][2] = max(9.0 + 1.0, 9.0) = 10.0
4dp[3][2] = max(9.0 + 1.5, 5.0 + 2.0, 5.0) = 11.0
5dp[4][2] = max(9.0 + 2.0, 5.0 + 3.0, 4.0 + 3.0, 4.0) = 12.0
6dp[5][2] = max(9.0 + 5.0, 5.0 + 6.0, 4.0 + 6.0, 3.75 + 9.0, 3.75) = 14.0

Finally we calculate for k = 3, we iterate for 2 < i < 5, for i = 3, the third group forms with the element at index 2, the second group forms with the element at index 1, and the first group forms with dp[1][1] Similarly we calculate for i = 4 and i = 5.

1
2
3dp[3][3] = max(9.0 + 1.0 + 2.0, 10.0 + 2.0, 10.0) = 12.0
4dp[4][3] = max(9.0 + 1.0 + 3.0, 10.0 + 3.0, 11.0 + 3.0, 11.0) = 14.0
5dp[5][3] = max(9.0 + 1.0 + 9.0, 10.0 + 9.0, 11.0 + 9.0, 12.0 + 9.0, 14.0) = 20.0

So the largest sum of Averages is 20.0

Python Solution

1
2python
3class Solution:
4    def largestSumOfAverages(self, A, K: int) -> float:
5        prefix = [0]*(len(A)+1)
6        for i in range(len(A)):
7            prefix[i+1] = prefix[i] + A[i]
8        
9        dp = [ [0]*(K+1) for _ in range(len(A)+1)]
10        
11        for i in range(1, len(A)+1):
12            dp[i][1] = prefix[i]/i
13        
14        for k in range(2, K+1):
15            for i in range(k, len(A)+1):
16                for j in range(k-1, i):
17                    dp[i][k] = max( dp[i][k], dp[j][k-1] + (prefix[i] - prefix[j]) / (i - j) )
18        return dp[len(A)][K]

Java Solution

1
2java
3class Solution {
4    public double largestSumOfAverages(int[] A, int K) {
5        int n = A.length;
6        double[] prefix = new double[n+1];
7        for(int i=0; i<n; i++)
8            prefix[i+1] = prefix[i] + A[i];
9
10        double[][] dp = new double[n+1][K+1];
11        for(int i=1; i<=n; i++)
12            dp[i][1] = prefix[i]/i;
13        
14        for(int k=2; k<=K; k++){
15            for(int i=k; i<=n; i++){
16                for(int j=k-1; j<i; j++)
17                    dp[i][k] = Math.max( dp[i][k], dp[j][k-1] + (prefix[i] - prefix[j]) / (i - j) );
18            }
19        }
20        return dp[n][K];
21    }
22}

Javascript Solution

1
2javascript
3var largestSumOfAverages = function(A, K) {
4    let n = A.length;
5        prefix = Array(n+1).fill(0);
6    for(let i=0; i<n; i++)
7        prefix[i+1] = prefix[i] + A[i];
8    
9    let dp = Array.from(Array(n+1), () => Array(K+1).fill(0));
10
11    for(let i=1; i<=n; i++)
12        dp[i][1] = prefix[i]/i;
13    
14    for(let k=2; k<=K; k++){
15        for(let i=k; i<=n; i++){
16            for(let j=k-1; j<i; j++)
17                dp[i][k] = Math.max( dp[i][k], dp[j][k-1] + (prefix[i] - prefix[j]) / (i - j) );
18        }
19    }
20    return dp[n][K];
21};

C++ Solution

1
2cpp
3class Solution {
4public:
5    double largestSumOfAverages(vector<int>& A, int K) {
6        int n = A.size();
7        vector<double> prefix(n+1, 0);
8        for(int i=0; i<n; i++)
9            prefix[i+1] = prefix[i] + A[i];
10        
11        vector<vector<double>> dp(n+1, vector<double>(K+1, 0));
12
13        for(int i=1; i<=n; i++)
14            dp[i][1] = prefix[i]/i;
15        
16        for(int k=2; k<=K; k++){
17            for(int i=k; i<=n; i++){
18                for(int j=k-1; j<i; j++)
19                    dp[i][k] = max( dp[i][k], dp[j][k-1] + (prefix[i] - prefix[j]) / (i - j) );
20            }
21        }
22        return dp[n][K];
23    }
24};

C# Solution

1
2csharp
3public class Solution {
4    public double LargestSumOfAverages(int[] A, int K) {
5        int n = A.Length;
6        double[] prefix = new double[n+1];
7        for(int i=0; i<n; i++)
8            prefix[i+1] = prefix[i] + A[i];
9        
10        double[,] dp = new double[n+1,K+1];
11
12        for(int i=1; i<=n; i++)
13            dp[i,1] = prefix[i]/i;
14        
15        for(int k=2; k<=K; k++){
16            for(int i=k; i<=n; i++){
17                for(int j=k-1; j<i; j++)
18                    dp[i,k] = Math.Max( dp[i,k], dp[j,k-1] + (prefix[i] - prefix[j]) / (i - j) );
19            }
20        }
21        return dp[n,K];
22    }
23}

Time and space complexity explanation

Time Complexity: O(n^2K), where n is the length of the list and K is the maximum number of groups. As there are nK combinations of different end positions and number of groups and it takes O(n) time to try all the last possible group positions.

Space Complexity: O(n*K), for storing the dp table dp[n][K].

This topic is an excellent exercise for the understanding of dynamic programming. We solve a complex problem by breaking it into simpler subproblems, solve each of them once, remember their solutions (memoization), and use the stored information to construct the solution to the original problem. It's also a valuable skill to know how to optimally divide a dataset into a subset of groups - whether it's for maximizing averages, minimizing variances, or other applications.

This skill can be useful in a variety of real-world applications, such as:

• Allocating resources optimally among various departments or projects in a company.
• Dividing a group of students into study groups to maximize the average score.
• Distribute tasks among workers to maximize the overall productivity.

Overall, mastering such problems can open the door to a wide range of algorithmic and real-world applications.