2026-09-29：K 个元素的最大总和。用go语言，有一个整数数组，另外给出两个整数 k 和 mul。需要从数组中取出正好 k 个数，这些数的处理顺

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

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

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

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

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

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

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

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

9. 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)。

package main

 import (
    "fmt"
    "slices"
)

 func maxSum(nums []int, k int, mul int) (ans int64) {
    slices.SortFunc(nums, func(a, b int)int { return b - a })
    for _, x := range nums[:k] {
        ans += int64(x) * int64(max(mul, 1))
        mul--
    }
    return
}

 func main() {
    nums := []int{3, 7, 5, 2}
    k := 2
    mul := 4
    result := maxSum(nums, k, mul)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 from typing import List

 def max_sum(nums: List[int], k: int, mul: int) -> int:
    nums.sort(reverse=True)
    ans = 0
    for x in nums[:k]:
        ans += x * max(mul, 1)
        mul -= 1
    return ans

 if __name__ == "__main__":
    nums = [3, 7, 5, 2]
    k = 2
    mul = 4
    result = max_sum(nums, k, mul)
    print(result)

C++完整代码如下：

  

  

  


 using namespace std;

 long long maxSum(vector& nums, int k, int mul) {
    // 降序排序
    sort(nums.begin(), nums.end(), greater());
    long long ans = 0;
    for (int i = 0; i < k; ++i) {
        int x = nums[i];
        ans += (long long)x * max(mul, 1);
        mul--;
    }
    return ans;
}

 int main() {
    vector nums = {3, 7, 5, 2};
    int k = 2;
    int mul = 4;
    long long result = maxSum(nums, k, mul);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。