原文链接: https://leetcode-cn.com/problems/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.

 

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:

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

中文题目

我们将给定的数组 A 分成 K 个相邻的非空子数组 ，我们的分数由每个子数组内的平均值的总和构成。计算我们所能得到的最大分数是多少。

注意我们必须使用 A 数组中的每一个数进行分组，并且分数不一定需要是整数。

示例:
输入: 
A = [9,1,2,3,9]
K = 3
输出: 20
解释: 
A 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20.
我们也可以把 A 分成[9, 1], [2], [3, 9].
这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.

说明:

• 1 <= A.length <= 100.
• 1 <= A[i] <= 10000.
• 1 <= K <= A.length.
• 答案误差在 10^-6 内被视为是正确的。

通过代码

官方题解

动态规划：

我们可以使用动态规划来解决这个问题。设 dp(i, k) 表示将数组 A 中的前 i 个元素 A[:i] 分成 k 个相邻的非空子数组，可以得到的最大分数。dp(i, k) 的值可以通过 dp(j, k - 1) 转移而来，其中 j < i，状态转移方程为：

dp(i, k) = max(dp(j, k - 1) + average(j + 1, i))
dp(i, 0) = average(0, i)

其中 average(j + 1, i) 表示 A[j + 1] 到 A[i] 的平均值 (A[j + 1] + A[j + 2] + ... + A[i]) / (i - j)。我们可以通过预处理出前缀和 P[x + 1] = A[0] + A[1] + ... + A[x]，从而用 average(j + 1, i) = (P[i + 1] - P[j + 1]) / (i - j) 在常数时间内得到平均值。

我们可以继续优化动态规划的空间复杂度。可以发现，如果设 dp(i, k) 为第 k 层的结果，那么第 k 层的结果实际上只和第 k - 1 层有关，因此我们可以使用滚动数组优化空间，即只使用两个一维数组。进一步而言。如果我们从后往前进行动态规划，即设 dp(i, k) 表示数组 A 中从第 i 个元素到结尾 A[i:] 分成 k 个相邻的非空子数组，可以得到的最大分数，那么状态转移方程将变为：

dp(i, k) = max(dp(j, k - 1) + average(i, j - 1))
dp(i, 0) = average(i, n - 1)

其中 j > i，那么我们在计算第 k 层的结果，并且 i 是依次递增的时候，第 k 层的结果并不会覆盖掉第 k - 1 层的结果，因为当 dp(i, k) 被计算出并且覆盖了 dp(i, k - 1) 时，接下来的所有 dp(i0, k), i0 > i 都不会从 dp(i, k - 1) 转移而来。因此我们最终只需要用一个一维数组，就能完成动态规划。

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

        double[] dp = new double[N];
        for (int i = 0; i < N; ++i)
            dp[i] = (P[N] - P[i]) / (N - i);

        for (int k = 0; k < K-1; ++k)
            for (int i = 0; i < N; ++i)
                for (int j = i+1; j < N; ++j)
                    dp[i] = Math.max(dp[i], (P[j]-P[i]) / (j-i) + dp[j]);

        return dp[0];
    }
}

[sol1]
class Solution(object):
    def largestSumOfAverages(self, A, K):
        P = [0]
        for x in A: P.append(P[-1] + x)
        def average(i, j):
            return (P[j] - P[i]) / float(j - i)

        N = len(A)
        dp = [average(i, N) for i in xrange(N)]
        for k in xrange(K-1):
            for i in xrange(N):
                for j in xrange(i+1, N):
                    dp[i] = max(dp[i], average(i, j) + dp[j])

        return dp[0]

复杂度分析

• 时间复杂度：$O(K * N^2)$，其中 $N$ 是数组 A 的长度。

• 空间复杂度：$O(N)$。

统计信息

通过次数	提交次数	AC比率
7401	13399	55.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言