查询建设工程规范的网站,wordpress并列插件,做视频直播的网站有哪些,平板室内装修设计软件1. 题目
我们将给定的数组 A 分成 K 个相邻的非空子数组 #xff0c;我们的分数由每个子数组内的平均值的总和构成。 计算我们所能得到的最大分数是多少。
注意我们必须使用 A 数组中的每一个数进行分组#xff0c;并且分数不一定需要是整数。
示例:
输入:
A [9,1,2,3,9…1. 题目
我们将给定的数组 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 内被视为是正确的。来源力扣LeetCode 链接https://leetcode-cn.com/problems/largest-sum-of-averages 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
dp[i][k] 表示以 i 结束的时候切分了k段所有平均值和的最大值预先求出前缀和 presumdp[j][k]max(dp[j][k],dp[i][k−1](presum[j]−presum[i])/double(j−i)),ijdp[j][k] \max(dp[j][k], dp[i][k-1](presum[j]-presum[i])/double(j-i)), i jdp[j][k]max(dp[j][k],dp[i][k−1](presum[j]−presum[i])/double(j−i)),ij
class Solution { //C
public:double largestSumOfAverages(vectorint A, int K) {int i, j, k, n A.size();vectorvectordouble dp(n,vectordouble(K1, 0.0));//dp[i][k] 表示以i结束的时候切分了k段所有平均值和的最大值vectorint presum(A);for(i 1; i n; i) presum[i] presum[i-1];for(i 0; i n-K; i)dp[i][1] presum[i]/double(i1);//初始化切1段出来的平均值for(k 2; k K; k){ //第k段for(j k-1; j n-(K-k); j){ //j 在第k段可能的范围for(i j-1; i 0; --i){ //遍历小于 j 的所有 idp[j][k] max(dp[j][k], dp[i][k-1](presum[j]-presum[i])/double(j-i));}}}return dp[n-1][K];}
};16 ms 8.3 MB
python3 解答
class Solution:# py3def largestSumOfAverages(self, A: List[int], K: int) - float:n len(A)dp [[0.0]*(K1) for _ in range(n)]for i in range(1,n):A[i] A[i-1]for i in range(n-K1):dp[i][1] A[i]/(i1)for k in range(2, K1):for j in range(k-1, n-(K-k)):for i in range(j):dp[j][k] max(dp[j][k], dp[i][k-1](A[j]-A[i])/(j-i))return dp[n-1][K]232 ms 13.8 MB
