0813-最大平均值和的分组

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 k 个非空子数组，且数组内部是连续的 。
分数 由每个子数组内的平均值的总和构成。

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

返回我们所能得到的最大 分数 是多少。答案误差在 10-6 内被视为是正确的。

示例 1:

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

示例 2:

**输入:** nums = [1,2,3,4,5,6,7], k = 4
**输出:** 20.50000

提示:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 104
  • 1 <= k <= nums.length

方法一：动态规划

命题：平均值和最大的分组的子数组数目必定是 k。

证明：假设一种分组的子数组数目小于 k，那么它必然有一个子数组的元素数目 c > 1，即仍然可以进行切分。设该子数组的平均值为 m，左侧第一个元素为 x，那么将该子数组第一个元素切分之后，平均值和为 \dfrac{m \times c - x}{c - 1} + x = \dfrac{c}{c - 1} \times m + \dfrac{c-2}{c-1} \times x > m，因此再次切分后平均值和会增加，所以平均值和最大的分组的子数组数目必定是 k。

为了方便计算子数组的平均值，我们使用一个数组 prefix 来保存数组 nums 的前缀和。我们使用 dp}[i][j] 表示 nums 在区间 [0, i-1] 被切分成 j 个子数组的最大平均值和，显然 i \ge j，计算分两种情况讨论：

  • 当 j = 1 时，dp}[i][j] 是对应区间 [0, i - 1] 的平均值；

  • 当 j > 1 时，我们将可以将区间 [0, i - 1] 分成 [0, x - 1] 和 [x, i - 1] 两个部分，其中 x \ge j-1，那么 dp}[i][j] 等于所有这些合法的切分方式的平均值和的最大值。

因此转移方程为：

\textit{dp}[i][j] =
\begin{cases}
\dfrac{\sum_{r = 0}^{i - 1}\textit{nums}[r]}{i}, & j = 1 \
\max\limits_{x \ge j - 1} {dp[x][j - 1] + \dfrac{\sum_{r = x}^{i - 1}\textit{nums}[r]}{i - x}}, & j > 1
\end{cases}

假设数组 nums 的长度为 n，那么 dp}[n][k] 表示数组 nums 分成 k 个子数组后的最大平均值和，即最大分数。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def largestSumOfAverages(self, nums: List[int], k: int) -> float:
        n = len(nums)
        prefix = list(accumulate(nums, initial=0))
        dp = [[0.0] * (k + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            dp[i][1] = prefix[i] / i
        for j in range(2, k + 1):
            for i in range(j, n + 1):
                for x in range(j - 1, i):
                    dp[i][j] = max(dp[i][j], dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x))
        return dp[n][k]
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<double> prefix(n + 1);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        vector<vector<double>> dp(n + 1, vector<double>(k + 1));
        for (int i = 1; i <= n; i++) {
            dp[i][1] = prefix[i] / i;
        }
        for (int j = 2; j <= k; j++) {
            for (int i = j; i <= n; i++) {
                for (int x = j - 1; x < i; x++) {
                    dp[i][j] = max(dp[i][j], dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x));
                }
            }
        }
        return dp[n][k];
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public double largestSumOfAverages(int[] nums, int k) {
        int n = nums.length;
        double[] prefix = new double[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        double[][] dp = new double[n + 1][k + 1];
        for (int i = 1; i <= n; i++) {
            dp[i][1] = prefix[i] / i;
        }
        for (int j = 2; j <= k; j++) {
            for (int i = j; i <= n; i++) {
                for (int x = j - 1; x < i; x++) {
                    dp[i][j] = Math.max(dp[i][j], dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x));
                }
            }
        }
        return dp[n][k];
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public double LargestSumOfAverages(int[] nums, int k) {
        int n = nums.Length;
        double[] prefix = new double[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        double[][] dp = new double[n + 1][];
        for (int i = 0; i <= n; i++) {
            dp[i] = new double[k + 1];
        }
        for (int i = 1; i <= n; i++) {
            dp[i][1] = prefix[i] / i;
        }
        for (int j = 2; j <= k; j++) {
            for (int i = j; i <= n; i++) {
                for (int x = j - 1; x < i; x++) {
                    dp[i][j] = Math.Max(dp[i][j], dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x));
                }
            }
        }
        return dp[n][k];
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define MAX(a, b) ((a) > (b) ? (a) : (b))

double largestSumOfAverages(int* nums, int numsSize, int k) {
    double prefix[numsSize + 1];
    prefix[0] = 0.0;
    for (int i = 0; i < numsSize; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    double dp[numsSize + 1][k + 1];
    for (int i = 1; i <= numsSize; i++) {
        dp[i][1] = prefix[i] / i;
    }
    for (int j = 2; j <= k; j++) {
        for (int i = j; i <= numsSize; i++) {
            dp[i][j] = 0.0;
            for (int x = j - 1; x < i; x++) {
                dp[i][j] = MAX(dp[i][j], dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x));
            }
        }
    }
    return dp[numsSize][k];
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var largestSumOfAverages = function(nums, k) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    const dp = new Array(n + 1).fill(0).map(() => new Array(k + 1).fill(0));
    for (let i = 1; i <= n; i++) {
        dp[i][1] = prefix[i] / i;
    }
    for (let j = 2; j <= k; j++) {
        for (let i = j; i <= n; i++) {
            for (let x = j - 1; x < i; x++) {
                dp[i][j] = Math.max(dp[i][j], dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x));
            }
        }
    }
    return dp[n][k];
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func largestSumOfAverages(nums []int, k int) float64 {
    n := len(nums)
    prefix := make([]float64, n+1)
    for i, x := range nums {
        prefix[i+1] = prefix[i] + float64(x)
    }
    dp := make([][]float64, n+1)
    for i := range dp {
        dp[i] = make([]float64, k+1)
    }
    for i := 1; i <= n; i++ {
        dp[i][1] = prefix[i] / float64(i)
    }
    for j := 2; j <= k; j++ {
        for i := j; i <= n; i++ {
            for x := j - 1; x < i; x++ {
                dp[i][j] = math.Max(dp[i][j], dp[x][j-1]+(prefix[i]-prefix[x])/float64(i-x))
            }
        }
    }
    return dp[n][k]
}

由于 dp}[i][j] 的计算只利用到 j-1 的数据，因此也可以使用一维数组对 dp}[i][j] 进行计算，在计算过程中，要注意对 i 进行逆序遍历。

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def largestSumOfAverages(self, nums: List[int], k: int) -> float:
        n = len(nums)
        prefix = list(accumulate(nums, initial=0))
        dp = [0.0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = prefix[i] / i
        for j in range(2, k + 1):
            for i in range(n, j - 1, -1):
                for x in range(j - 1, i):
                    dp[i] = max(dp[i], dp[x] + (prefix[i] - prefix[x]) / (i - x))
        return dp[n]
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<double> prefix(n + 1);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        vector<double> dp(n + 1);
        for (int i = 1; i <= n; i++) {
            dp[i] = prefix[i] / i;
        }
        for (int j = 2; j <= k; j++) {
            for (int i = n; i >= j; i--) {
                for (int x = j - 1; x < i; x++) {
                    dp[i] = max(dp[i], dp[x] + (prefix[i] - prefix[x]) / (i - x));
                }
            }
        }
        return dp[n];
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public double largestSumOfAverages(int[] nums, int k) {
        int n = nums.length;
        double[] prefix = new double[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        double[] dp = new double[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = prefix[i] / i;
        }
        for (int j = 2; j <= k; j++) {
            for (int i = n; i >= j; i--) {
                for (int x = j - 1; x < i; x++) {
                    dp[i] = Math.max(dp[i], dp[x] + (prefix[i] - prefix[x]) / (i - x));
                }
            }
        }
        return dp[n];
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public double LargestSumOfAverages(int[] nums, int k) {
        int n = nums.Length;
        double[] prefix = new double[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        double[] dp = new double[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = prefix[i] / i;
        }
        for (int j = 2; j <= k; j++) {
            for (int i = n; i >= j; i--) {
                for (int x = j - 1; x < i; x++) {
                    dp[i] = Math.Max(dp[i], dp[x] + (prefix[i] - prefix[x]) / (i - x));
                }
            }
        }
        return dp[n];
    }
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define MAX(a, b) ((a) > (b) ? (a) : (b))

double largestSumOfAverages(int* nums, int numsSize, int k) {
    double prefix[numsSize + 1];
    prefix[0] = 0.0;
    for (int i = 0; i < numsSize; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    double dp[numsSize + 1];
    for (int i = 1; i <= numsSize; i++) {
        dp[i] = prefix[i] / i;
    }
    for (int j = 2; j <= k; j++) {
        for (int i = numsSize; i >= j; i--) {
            for (int x = j - 1; x < i; x++) {
                dp[i] = MAX(dp[i], dp[x] + (prefix[i] - prefix[x]) / (i - x));
            }
        }
    }
    return dp[numsSize];
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var largestSumOfAverages = function(nums, k) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    const dp = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        dp[i] = prefix[i] / i;
    }
    for (let j = 2; j <= k; j++) {
        for (let i = n; i >= j; i--) {
            for (let x = j - 1; x < i; x++) {
                dp[i] = Math.max(dp[i], dp[x] + (prefix[i] - prefix[x]) / (i - x));
            }
        }
    }
    return dp[n];
};
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func largestSumOfAverages(nums []int, k int) float64 {
    n := len(nums)
    prefix := make([]float64, n+1)
    for i, x := range nums {
        prefix[i+1] = prefix[i] + float64(x)
    }
    dp := make([]float64, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = prefix[i] / float64(i)
    }
    for j := 2; j <= k; j++ {
        for i := n; i >= j; i-- {
            for x := j - 1; x < i; x++ {
                dp[i] = math.Max(dp[i], dp[x]+(prefix[i]-prefix[x])/float64(i-x))
            }
        }
    }
    return dp[n]
}

复杂度分析

  • 时间复杂度：O(k \times n^2)，其中 k 是分组的最大子数组数目，n 是数组 nums 的长度。计算前缀和需要 O(n) 的时间，动态规划需要计算 O(k \times n) 个状态，每个状态的计算时间是 O(n)。

  • 空间复杂度：O(k \times n) 或 O(n)，其中 k 是分组的最大子数组数目，n 是数组 nums 的长度。二维数组实现的空间复杂度是 O(k \times n)，一维数组实现的空间复杂度是 O(n)。

 Comments
On this page
0813-最大平均值和的分组