LeetCode 0813. 最大平均值和的分组
admin
2024-02-26 23:30:18
0次

【LetMeFly】813.最大平均值和的分组

力扣题目链接:https://leetcode.cn/problems/largest-sum-of-averages/

给定数组 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

方法一:DP + 前缀和

首先需要明白的是,虽然题目说的是“最多kkk组”,但其实等价于“分为kkk组”。因为能分成kkk组的话,绝对不分成k−1k-1k−1组。毕竟分组越少,除得越多。如果明白这个道理,下面的 证明 可以跳过。

证明:假设我们把数组分成了k−1k-1k−1组,那么我们可以将其中的某组一分为二(一定存在元素个数大于111的分组),这样,分母就会变小。(假设这组为[a1,a2,⋯,an,b][a_1, a_2, \cdots, a_n, b][a1​,a2​,⋯,an​,b],那么这组的平均数为a1+a2+⋯+an+bn+1\frac{a_1+a_2+\cdots+a_n+b}{n+1}n+1a1​+a2​+⋯+an​+b​,不失一般性,我们把其中的bbb分出来,这样平均数之和就变成了a1+a2+⋯+ann+b>a1+a2+⋯+an+bn+1\frac{a_1+a_2+\cdots+a_n}{n}+b>\frac{a_1+a_2+\cdots+a_n+b}{n+1}na1​+a2​+⋯+an​​+b>n+1a1​+a2​+⋯+an​+b​

目的明确,确定分为kkk组。因此我们就可以使用数组dp[n+1][k+1]dp[n+1][k+1]dp[n+1][k+1](其中nnn是数组中元素的个数),其中dp[i][j]dp[i][j]dp[i][j]代表将原始数组中的前iii个元素分为jjj组的最大“平均数之和”

我们预处理求出一个前缀和数组prefix[n+1]prefix[n+1]prefix[n+1],其中prefix[i]prefix[i]prefix[i]代表数组中前iii个元素的和

  • 当j=1j=1j=1时,dp[i][j]=dp[i][1]=prefix[i]/idp[i][j] = dp[i][1] = prefix[i] / idp[i][j]=dp[i][1]=prefix[i]/i(前iii个元素的平均数)
  • 否则,我们在[j−1,i−1][j-1, i-1][j−1,i−1]中挑选一个lll,将[0,i][0, i][0,i]分为[0,l−1][0, l-1][0,l−1]和[l,i−1][l,i-1][l,i−1]两部分,因此dp[i][j]=max⁡l≥j−1{dp[l][j−1]+∑r=li−1nums[r]i−l}dp[i][j]=\max_{l\geq j-1}\{dp[l][j-1]+\frac{\sum_{r=l}^{i-1}nums[r]}{i-l}\}dp[i][j]=maxl≥j−1​{dp[l][j−1]+i−l∑r=li−1​nums[r]​}

最终dp[n][k]dp[n][k]dp[n][k]即为答案

  • 时间复杂度O(n2×k)O(n^2\times k)O(n2×k)
  • 空间复杂度O(n×k)O(n\times k)O(n×k)

AC代码

C++

class Solution {
public:double largestSumOfAverages(vector& nums, int k) {int n = nums.size();vector prefix(n + 1);for (int i = 1; i <= n; i++) {prefix[i] = prefix[i - 1] + nums[i - 1];}vector> dp(n + 1, vector(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 l = j - 1; l < i; l++) {dp[i][j] = max(dp[i][j], dp[l][j - 1] + (prefix[i] - prefix[l]) / (i - l));}}}return dp[n][k];}
};

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/128087654

相关内容

热门资讯

WePoKer透视挂教程!wp... WePoKer透视挂教程!wpk作弊最怕三个东西”好像真的是有透视挂要领1、该软件可以轻松地帮助玩家...
德扑之星透视挂攻略!德扑之星有... 德扑之星透视挂攻略!德扑之星有透视辅助吗”竟然是真的有透视挂方式1、德扑之星有透视辅助吗模拟器是什么...
微扑克辅助器技巧!AApoke... 微扑克辅助器技巧!AApoker插件”竟然存在有辅助器课程1)微扑克辅助有没有挂:进一步探索微扑克辅...
AApoker辅助器app!A... AApoker辅助器app!AApoker选牌”好像真的是有辅助器积累AApoker辅助器是不是有人...
aapoker辅助器app!大... aapoker辅助器app!大菠萝辅助器”切实是有辅助器总结aapoker辅助器app!大菠萝辅助器...
菠萝智星德州开挂插件!aapo... 菠萝智星德州开挂插件!aapoker辅助软件合法吗”果然存在有开挂技法aapoker辅助软件合法吗是...
微扑克辅助神器!哈糖大菠萝辅助... 微扑克辅助神器!哈糖大菠萝辅助器”竟然存在有辅助手段1、哈糖大菠萝辅助器免费脚本咨询教程、哈糖大菠萝...
WPK辅助器教程!德扑辅助器怎... WPK辅助器教程!德扑辅助器怎么用”总是是真的有辅助器手册1、玩家可以在德扑辅助器怎么用线上大神俱乐...
智星菠萝德州开挂神器!如何判断... 智星菠萝德州开挂神器!如何判断wpk辅助软件的真假”一贯真的有开挂窍要1、打开软件启动之后找到中间准...
菠萝智星德州透视插件!AApo... 菠萝智星德州透视插件!AApoker抽水”本来是真的有透视诀窍1、玩家可以在德州透视插件线上大神俱乐...