algoadvance

Leetcode 813. Largest Sum of Averages

Problem Statement

You are given an integer array A and an integer K. You can partition the array into at most K non-empty adjacent subarrays, and the score of a partition is the sum of the averages of each subarray. Determine the largest sum of averages you can achieve.

Example:

• Input: A = [9,1,2,3,9], K = 3
• Output: 20

Explanation:

• The optimal partition is [9], [1, 2, 3], [9] with the corresponding averages 9, 2, and 9 respectively. Hence, the result is 9 + 2 + 9 = 20.

Constraints:

• 1 <= A.length <= 100
• 1 <= A[i] <= 10000
• 1 <= K <= A.length

Clarifying Questions

1. Can K be larger than the length of the array A?
   • No, K will always be less than or equal to the length of A.
2. Are the integers all positive?
   • Yes, as per the constraint 1 <= A[i] <= 10000.
3. Should the result be a floating point number or an integer?
   • The result should be a floating point number as averages might not be integers.

Strategy

1. Use Dynamic Programming to solve the problem.
2. Define dp[i][k] as the maximum sum of averages we can achieve for the first i elements with k partitions.
3. Compute cumulative sums to efficiently calculate the sum of any subarray.
4. Transition:
   • If you are at index i and making a partition at j, the new state can be derived using dp[j][k-1] plus the average of subarray [j+1, i].
5. Initialize the cumulated sum array.
6. Fill the dynamic programming table based on transitions.

Code

#include <vector>
#include <numeric>
#include <iostream>
 
using namespace std;

class Solution {
public:
    double largestSumOfAverages(vector<int>& A, int K) {
        int n = A.size();
        vector<double> prefixSum(n + 1, 0.0);
        for (int i = 0; i < n; ++i) {
            prefixSum[i + 1] = prefixSum[i] + A[i];
        }

        vector<vector<double>> dp(n + 1, vector<double>(K + 1, 0.0));

        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] = max(dp[i][k], dp[j][k - 1] + (prefixSum[i] - prefixSum[j]) / (i - j));
                }
            }
        }
        
        return dp[n][K];
    }
};

Time Complexity

• Time Complexity: O(n^2 * K), where n is the length of array A. This results from three nested loops: the outer loop iterates over K (partitions), and the two inner loops (one to fix the end of the subarray and one to iterate over possible start points).
• Space Complexity: O(n * K), due to the DP table dp and the prefix sum array.

This solution efficiently computes the largest sum of averages by leveraging dynamic programming and prefix sums to reduce redundant calculations.

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?