网易首页 > 网易号 > 正文 申请入驻

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

0
分享至

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

Go完整代码如下:

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助力您的未来发展。

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相关推荐
热点推荐
不得不说,这个画面拍得非常好,特朗普新飞机和解放军仪仗队同框

不得不说,这个画面拍得非常好,特朗普新飞机和解放军仪仗队同框

三叔的装备空间
2026-11-19 13:55:23
日媒称高市早苗在机场受到中方“简朴迎接”引发关注,外交部:作为东道主,中方根据国际惯例,对所有参会方作出适当的礼宾安排

日媒称高市早苗在机场受到中方“简朴迎接”引发关注,外交部:作为东道主,中方根据国际惯例,对所有参会方作出适当的礼宾安排

政知新媒体
2026-11-19 15:22:03
特朗普刚走,留守白宫的万斯,一谈到中国时,尽显总统的风范

特朗普刚走,留守白宫的万斯,一谈到中国时,尽显总统的风范

共工之锚
2026-11-19 10:58:14
25名华人跟团来澳洲, 偷偷逃走! 一团20多人全跑光, 剩领队风中凌乱! 300万押金直接不要?

25名华人跟团来澳洲, 偷偷逃走! 一团20多人全跑光, 剩领队风中凌乱! 300万押金直接不要?

澳微Daily
2026-11-19 12:51:32
我国出口的7吨出口大闸蟹被退运,检出 “世纪之毒”?啥情况?

我国出口的7吨出口大闸蟹被退运,检出 “世纪之毒”?啥情况?

狸猫之一的动物圈
2026-11-19 09:00:33
普京和特朗普都已放话,只要人来了深圳,绝对不会错过金正恩

普京和特朗普都已放话,只要人来了深圳,绝对不会错过金正恩

漫步独行侠
2026-11-19 09:25:33
马斯克再带小儿子来中国,笑称他的玩具都是“中国造”:“我是中国的超级粉丝,中国很酷。”

马斯克再带小儿子来中国,笑称他的玩具都是“中国造”:“我是中国的超级粉丝,中国很酷。”

都市快报橙柿互动
2026-11-19 13:37:19
美国人评价中国深圳:环境很好,街道干净,不过一点比不上美国!

美国人评价中国深圳:环境很好,街道干净,不过一点比不上美国!

扶苏聊历史
2026-11-19 11:35:42
网易号平台每日辟谣公告(十一月十八日)

网易号平台每日辟谣公告(十一月十八日)

网易号官方平台
2026-11-18 19:08:14
APEC 封神!别家啃冷三明治,深圳直接上现炒热菜,老外记者看呆,深圳媒体中心这顿饭,把老外 CPU 干烧了

APEC 封神!别家啃冷三明治,深圳直接上现炒热菜,老外记者看呆,深圳媒体中心这顿饭,把老外 CPU 干烧了

魔都姐姐杂谈
2026-11-19 10:30:45
“风流尼姑”释智定:贪财好色与两个和尚结婚,私生活混乱住豪宅

“风流尼姑”释智定:贪财好色与两个和尚结婚,私生活混乱住豪宅

夜话奇谭
2026-11-19 14:39:47
苹果新iPhone屏幕公布,几乎无边框!

苹果新iPhone屏幕公布,几乎无边框!

科技堡垒
2026-11-19 08:00:44
就在中国深圳!普京与特朗普见面握手并合影

就在中国深圳!普京与特朗普见面握手并合影

看看新闻Knews
2026-11-18 23:46:04
永州女局长风波偃旗息鼓:一个多月过去,官宣核查下,公众还要等多久

永州女局长风波偃旗息鼓:一个多月过去,官宣核查下,公众还要等多久

十为先生
2026-11-18 15:41:00
震惊!美调查显示,14%受访者押注做空中国股票,该交易半年来首次上榜,引发热议

震惊!美调查显示,14%受访者押注做空中国股票,该交易半年来首次上榜,引发热议

火山詩话
2026-11-19 06:30:57
深圳女高管和每一任男友发生关系前,都要先拉他去体检,防止被传染

深圳女高管和每一任男友发生关系前,都要先拉他去体检,防止被传染

江山挥笔
2026-11-19 14:15:33
宁德向理想一天发3封要钱邮件 :战略合作伙伴的体面,是按“封”计算的!

宁德向理想一天发3封要钱邮件 :战略合作伙伴的体面,是按“封”计算的!

城事堂
2026-11-19 08:54:42
日俄见面了!普京只给30分钟,高市当面说的话,让俄罗斯不咋高兴

日俄见面了!普京只给30分钟,高市当面说的话,让俄罗斯不咋高兴

共工之锚
2026-11-19 11:05:09
“谢霆锋现在的心情,估计比吃了苍蝇还难受。原来,张柏芝离开他后,越过越风生水起了…”

“谢霆锋现在的心情,估计比吃了苍蝇还难受。原来,张柏芝离开他后,越过越风生水起了…”

黎兜兜
2026-11-19 16:12:44
闹掰了?有理想员工称“一天收宁德时代三封催债邮件”,8月从宁德前五大客户中消失

闹掰了?有理想员工称“一天收宁德时代三封催债邮件”,8月从宁德前五大客户中消失

红星新闻
2026-11-19 14:51:15
2026-11-19 18:11:00
moonfdd incentive-icons
moonfdd
福大大架构师每日一题
1584文章数 83关注度
往期回顾 全部

科技要闻

老黄想回来?英伟达董事会:没门

头条要闻

中国女子在希腊失踪半年 保险箱发现10万欧元现金

头条要闻

中国女子在希腊失踪半年 保险箱发现10万欧元现金

体育要闻

伪强队?拥4亿豪阵欧国联6连败+世界杯出局

娱乐要闻

陈晓楠对话厉娜和许飞引全网热议

财经要闻

10万人逼宫英伟达,黄仁勋要复职了?

汽车要闻

全新红旗H9最有意思的地方,是它开始有自己的豪华逻辑了

态度原创

游戏
家居
数码
手机
军事航空

PC Gamer试玩GTA6百小时:双主角出色但任务重复

家居要闻

2026建博会(广州) 公装联探展交流活动

数码要闻

苹果公布2026古典乐年度专辑:任奫灿《哥德堡变奏曲》获奖

手机要闻

2026年最后一款超模旗舰!小米18标准版屏幕、性能、影像全面领跑

军事要闻

美军在中东再成三航母之势

无障碍浏览 进入关怀版