LeetCode解题报告（487）-- 813. Largest Sum of Averages

Problem

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.

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:

1 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

Analysis

题目给出一个数组nums，还有一个k，问把数组至多分成k个subarray，使得每个subarray的平均值加起来最大是多少。这种一看是subarray又是求最值的问题，还是两个方向，sliding window或者dp。因为对于subarray没有长度的限制，也没有数值上的限制，所以sliding window并不是适用，于是我们就focus到dp上。数组类的dp一般有一个状态就是i，另一个状态就是k，但这里实际上是k - 1，因为分成k组就是做k - 1次分割。

先来看第一个状态i，一般我们会定义i是[0, i]这样，但是这道题目有点不一样，我们定义的是[i, n-1]，为什么要这样定义呢？因为这样用presum计算方便，假设我们要计算dp[i][k],我们遍历j，j的范围是[i + 1, n]，那么dp[i][k] = max(dp[i][k], average(i, j) + dp[j][k - 1])。到这里我们其实已经可以写出转移方程了。

然后来看两个可优化的部分，第一个部分是求平均数，前面提到用presum计算，所以我们可以先计算出一个presum的数组，求average(i, j) = (preSum[j] - preSum[i]) / (j - i)（注意这个是不包含nums[j]的）。第二个部分是dp方程，可以看出我们每次都需要计算完所有的k - 1，再计算k，所以我们只用一个状态就可以了，可以把k这个状态省略掉。

Solution

无。

Code

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int K) {
        int size = nums.size();
        vector<int> preSum(size + 1, 0);
        for (int i = 1; i <= size; ++i) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        
        vector<double> dp(size, 0.0);
        for (int i = 0; i < size; ++i) {
            dp[i] = (1.0 * (preSum[size] - preSum[i])) / (size - i);
        }
        
        for (int k = 0; k < K - 1; ++k) {
            for (int i = 0; i < size; ++i) {
                for (int j = i + 1; j < size; ++j) {
                    dp[i] = max(dp[i], dp[j] + (1.0 * (preSum[j] - preSum[i])) / (j - i));
                }
            }
        }
        return dp[0];
    }
};

Summary

这道题目是比较常规的数组dp，里面包含了用presum计算平均数以及dp空间优化，是一道好题。在二维矩阵中使用并查集要注意下标转换，同时还要特别注意初始化的时机。这道题目的分享到这里，感谢你的支持！