企业官网建设流程全解析

2026-09-29：K 个元素的最大总和。用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。

分步骤详细描述整个过程：

1. 准备输入数据
   有一个整数数组 nums，一个整数 k，一个整数 mul。
   nums 中每个元素都是正数（1 到 100000），k 表示要选出的元素个数，mul 是初始的乘数。

2. 对数组进行降序排序
   把 nums 中的所有元素按照从大到小的顺序排列。
   这样做的原因是：后面每个被选中的元素会依次对应一个乘数，而这个乘数是递减的（先是 mul，然后 mul-1，再然后 mul-2……直到变成 1，之后如果还有元素就保持为 1）。为了让总和最大，应该把最大的数分配给最大的乘数，把较小的数分配给较小的乘数。降序排序正好满足这个要求。

3. 初始化总和
   定义一个变量用来保存最终的总和，初始值为 0。

4. 遍历排序后数组的前 k 个元素
   因为只需要恰好 k 个元素，所以直接从排序后的数组开头取 k 个即可。
   依次处理这 k 个元素，每处理一个，就把它对总和的贡献加进去。

5. 对每个元素计算有效乘数
   当前有一个乘数 mul。
   对于当前元素 x，判断应该用哪个乘数来乘它。
   如果当前 mul 大于等于 1，那么乘以 mul 会让结果变大（因为 x 是正数），所以直接使用 mul。
   如果当前 mul 小于等于 0，乘以它会让结果变成零或负数，这显然不如直接加 x 本身，所以这时把有效乘数视为 1。
   换句话说，有效乘数就是 mul 和 1 中的较大值。

6. 累加贡献
   把当前元素 x 乘以这个有效乘数，得到一个贡献值。
   把这个贡献值加到总和变量中。

7. 更新 mul
   每处理完一个元素，无论刚才用了哪种方式，mul 都要自动减 1。
   这样下一个元素面对的就是比之前小 1 的乘数。
   如果 mul 已经很小，减到 0 或负数也没关系，因为下一步计算有效乘数时会用 1 来替代。

8. 循环直到处理完 k 个元素
   重复第 5 到第 7 步，直到前 k 个元素全部处理完毕。

9. 返回总和
   最终得到的总和就是可能的最大总和，直接返回。

为什么这样能得到最大值？
因为所有 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("fmt""slices")funcmaxSum(nums[]int,kint,mulint)(ansint64){slices.SortFunc(nums,func(a,bint)int{returnb-a})for_,x:=rangenums[:k]{ans+=int64(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(reverse=True)ans=0forxinnums[:k]:ans+=x*max(mul,1)mul-=1returnansif__name__=="__main__":nums=[3,7,5,2]k=2mul=4result=max_sum(nums,k,mul)print(result)

C++完整代码如下：

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;longlongmaxSum(vector<int>&nums,intk,intmul){// 降序排序sort(nums.begin(),nums.end(),greater<int>());longlongans=0;for(inti=0;i<k;++i){intx=nums[i];ans+=(longlong)x*max(mul,1);mul--;}returnans;}intmain(){vector<int>nums={3,7,5,2};intk=2;intmul=4;longlongresult=maxSum(nums,k,mul);cout<<result<<endl;return0;}