algoadvance

Leetcode 813. Largest Sum of Averages

Problem Statement

You are given an integer array A and an integer K. You need to split the array into K non-empty continuous subarrays to maximize the sum of the averages of each subarray.

Return the largest sum of averages.

Example:

Input: A = [9,1,2,3,9], K = 3
Output: 20.0
Explanation:
The best choice is to split into [9], [1, 2, 3], [9]. 
So the result is 9 + (1+2+3)/3 + 9 = 20.

Note:

1. 1 <= A.length <= 100.
2. 1 <= A[i] <= 10000.
3. 1 <= K <= A.length.
4. The answer will be calculated within the range of a decimal number.

Clarifying Questions:

1. Is the division of subarrays required to be contiguous?
   • Yes, they must be contiguous subarrays.
2. Should the result be rounded to a particular number of decimal places?
   • No, just return the result as a floating-point number.

Strategy:

1. Dynamic Programming (DP) Approach:
   • Let’s use a DP table dp[i][k] where dp[i][k] represents the maximum sum of averages we can get by partitioning the first i elements into k parts.
   • Define prefixSum[i] as the sum of the first i elements of array A.
   • The relation can be derived as follows:
     • For every possible last partition ending at j (where j < i), we calculate the sum of averages as: dp[i][k] = max(dp[i][k], dp[j][k-1] + avg(j+1, i)).
     • Here, avg(j+1, i) = (prefixSum[i] - prefixSum[j]) / (i - j).
   • We initialize the DP array such that dp[i][1] represents the average of the first i elements.

Code:

public class Solution {
    public double largestSumOfAverages(int[] A, int K) {
        int N = A.length;
        double[] prefixSum = new double[N+1];
        for (int i = 0; i < N; i++) {
            prefixSum[i+1] = prefixSum[i] + A[i];
        }

        double[][] dp = new double[N+1][K+1];
        
        for (int i = 1; i <= N; i++) {
            dp[i][1] = prefixSum[i] / i;
        }
        
        for (int k = 2; k <= K; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 0; j < i; j++) {
                    dp[i][k] = Math.max(dp[i][k], dp[j][k-1] + (prefixSum[i] - prefixSum[j]) / (i - j));
                }
            }
        }
        
        return dp[N][K];
    }
}

Time Complexity:

• The time complexity is O(N^2 * K):
  • There are N*K states to fill in the DP table.
  • Each state (dp[i][k]) takes O(N) time to compute the maximum.
• Space Complexity:
  • The space complexity is O(N*K) for the dp array and O(N) for the prefixSum array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?