2026-09-29K 个元素的最大总和。用go语言有一个整数数组另外给出两个整数 k 和 mul。需要从数组中取出正好 k 个数这些数的处理顺序可以自行安排。处理每一个被选中的数时有两种方式可以任选一种一种是把该数本身直接加入总分另一种是把该数乘以当时 mul 的值再把乘积加入总分。每处理完一个数不管刚才选的是哪种方式mul 都会自动减一因此它可能变成零也可能变成负数。目标是让最终得到的总和尽可能大并返回这个最大的总和。1 nums.length 100000。1 nums[i] 100000。1 k nums.length。1 mul 100000。输入 nums [3,7,5,2], k 2, mul 4。输出 43。解释一种最优方式如下一种最优选择是 nums[1] 7 和 nums[2] 5。先处理 nums[1] 7选择乘法因此贡献 7 * 4 28。此时mul 变为 3。接着处理 nums[2] 5选择乘法因此贡献 5 * 3 15。总和为 28 15 43。题目来自力扣3974。分步骤详细描述整个过程准备输入数据有一个整数数组 nums一个整数 k一个整数 mul。nums 中每个元素都是正数1 到 100000k 表示要选出的元素个数mul 是初始的乘数。对数组进行降序排序把 nums 中的所有元素按照从大到小的顺序排列。这样做的原因是后面每个被选中的元素会依次对应一个乘数而这个乘数是递减的先是 mul然后 mul-1再然后 mul-2……直到变成 1之后如果还有元素就保持为 1。为了让总和最大应该把最大的数分配给最大的乘数把较小的数分配给较小的乘数。降序排序正好满足这个要求。初始化总和定义一个变量用来保存最终的总和初始值为 0。遍历排序后数组的前 k 个元素因为只需要恰好 k 个元素所以直接从排序后的数组开头取 k 个即可。依次处理这 k 个元素每处理一个就把它对总和的贡献加进去。对每个元素计算有效乘数当前有一个乘数 mul。对于当前元素 x判断应该用哪个乘数来乘它。如果当前 mul 大于等于 1那么乘以 mul 会让结果变大因为 x 是正数所以直接使用 mul。如果当前 mul 小于等于 0乘以它会让结果变成零或负数这显然不如直接加 x 本身所以这时把有效乘数视为 1。换句话说有效乘数就是 mul 和 1 中的较大值。累加贡献把当前元素 x 乘以这个有效乘数得到一个贡献值。把这个贡献值加到总和变量中。更新 mul每处理完一个元素无论刚才用了哪种方式mul 都要自动减 1。这样下一个元素面对的就是比之前小 1 的乘数。如果 mul 已经很小减到 0 或负数也没关系因为下一步计算有效乘数时会用 1 来替代。循环直到处理完 k 个元素重复第 5 到第 7 步直到前 k 个元素全部处理完毕。返回总和最终得到的总和就是可能的最大总和直接返回。为什么这样能得到最大值因为所有 nums 中的数都是正数而乘数序列是单调不增的先是 mul, mul-1, mul-2, …降到 1 之后就一直是 1。对于正数来说越大的数乘以越大的乘数对总和的贡献越大。所以把最大的数放在最前面让它享受最大的乘数依次类推就能让总和最大化。时间复杂度和额外空间复杂度时间复杂度主要消耗在排序上。数组长度为 n排序需要 O(n log n) 的时间。排序之后只需要遍历前 k 个元素时间复杂度为 O(k)。因为 k ≤ n所以总时间复杂度为 O(n log n)。额外空间复杂度算法本身除了输入数组外只使用了常数个变量总和、循环变量、当前乘数等没有开辟与 n 或 k 成比例的额外空间。排序过程如果是原地排序通常只需要 O(log n) 的递归栈空间比如快速排序的递归深度。因此额外空间复杂度可以认为是 O(1)不考虑排序递归栈或者严格说为 O(log n)包含排序的栈空间。但通常在这种算法分析中会表述为额外空间 O(1)。Go完整代码如下packagemainimport(fmtslices)funcmaxSum(nums[]int,kint,mulint)(ansint64){slices.SortFunc(nums,func(a,bint)int{returnb-a})for_,x:rangenums[:k]{ansint64(x)*int64(max(mul,1))mul--}return}funcmain(){nums:[]int{3,7,5,2}k:2mul:4result:maxSum(nums,k,mul)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromtypingimportListdefmax_sum(nums:List[int],k:int,mul:int)-int:nums.sort(reverseTrue)ans0forxinnums[:k]:ansx*max(mul,1)mul-1returnansif__name____main__:nums[3,7,5,2]k2mul4resultmax_sum(nums,k,mul)print(result)C完整代码如下#includeiostream#includevector#includealgorithmusingnamespacestd;longlongmaxSum(vectorintnums,intk,intmul){// 降序排序sort(nums.begin(),nums.end(),greaterint());longlongans0;for(inti0;ik;i){intxnums[i];ans(longlong)x*max(mul,1);mul--;}returnans;}intmain(){vectorintnums{3,7,5,2};intk2;intmul4;longlongresultmaxSum(nums,k,mul);coutresultendl;return0;}