[Leetcode] 813. Largest Sum of Averages

813. Largest Sum of Averages

You are given an integer array nums and an integer k. You can partition the array into at most k non-empty adjacent subarrays. The score of a partition is the sum of the averages of each subarray.

Note that the partition must use every integer in nums, and that the score is not necessarily an integer.

Return the maximum score you can achieve of all the possible partitions. Answers within 10-6 of the actual answer will be accepted.

Constraints:

1 <= nums.length <= 100

1 <= nums[i] <= 10^4

1 <= k <= nums.length

Analysis:

This question asks for the an maximum value, so we usually can consider dp first.

As it is known, the key for dp is to find the transition formula. Or find the key parameters than describe an "intermediate state" completely.

The intermediate state here represents a similar question but with a smaller size.

For this question, we can try to define the state as dp[i][k], where i is the index of the elements and k is the number of subarrays.

The meaning of dp[i][k] is the maximum of average sum ending with the ith element with at most k subarrays.

Then the next step is to derive the formula to calculate the value of dp[i][k] using the previous dp with smaller values of i and k.

dp[i][k] = max(dp[x][k-1] + sum(num[x+1] to nums[i])/(i-x)), where x from 0 to i-1.

With the meaning of dp[x][k-1], the above formula is not hard to understand:

The right-hand side (rhs) enumerates all the possible ways to calculate dp[i][k], so we just need to pick up the maximum of it.

In the implementation, the boundary conditions are tricky. The thumb rule is to make sure the dp[i][k] is valid. For example, dp[i>0][0] is not valid, since there is no such case that we have non-zero elements in 0 subarray.

See the code below:

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        // dp[i][j]: the max, ending at i, up to j subarray;
        // dp[i][j] = max(dp[d][j-1] + sum(nums[d+1], ..., nums[i])/(i-d))
        // where d from j-1 to i-1.
        double res = 0;
        int n = nums.size();
        vector<double> sums(n+1, 0);
        for(int i=0; i<n; ++i) sums[i+1] = sums[i] + nums[i];
        vector<vector<double>> dp(n+1, vector<double>(k+1, 0));
        for(int i=1; i<=n; ++i) {
            for(int j=min(i, k); j>=1; --j) {
                for(int d=max(j-1, 1); d<=i; ++d) {
                    double v = (j==1&&d>1) ? 0 : (dp[d-1][j-1] + (sums[i]-sums[d-1])/(i-d+1));
                    dp[i][j] = max(dp[i][j], v);
                }
            }
        }
        return dp[n][k];
    }
};

If do not like the boundary conditions of the above dp solution, we can try dfs + memoization.

We can start from the beginning of the array, and stop to make a subarray at any possible places.

See the code below:

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<double>> memo(n, vector<double>(k, -1));
        return dfs(nums, 0, k-1, memo);
    }
private:
    double dfs(vector<int>& ns, int id, int k, vector<vector<double>>& memo) {
        // invalid ending since we cannot have more than k subarrays
        if(k<0 && id<ns.size()) return -2;
        if(id==ns.size()) return 0;
        if(memo[id][k] != -1) return memo[id][k];
        double t = 0, sum = 0;
        for(int i=id; i<ns.size(); ++i) {
            sum += ns[i];
            double v = dfs(ns, i+1, k-1, memo);
            if(v>-2) t = max(t, sum/(i-id+1) + v);
        }
        return memo[id][k] = t;
    }
};