- 主题:问个算法题
三个数组 每个数组m个数(没按大小排序)
要求从三个数组中找出m个数的和的最大值,每个数组可以取0到m个数,但必须是该数组的前几个数连续取
怎么做,不用暴力解法的话
※ 修改:·yellowChange 于 Sep 17 17:03:05 2021 修改本文·[FROM: 114.253.76.*]
※ 来源:·最水木 客户端·[FROM: 114.253.76.*]
修改:yellowChange FROM 114.253.76.*
FROM 114.253.76.*
别无他法。
【 在 yellowChange (yellowChange) 的大作中提到: 】
: 三个数组 每个数组m个数(没按大小排序)
: 要求从三个数组中找出m个数的和的最大值,每个数组可以取0到m个数,但必须是该数组的前几个数连续取
: 怎么做,不用暴力解法的话
: ...................
--
FROM 49.74.84.*
确定?
【 在 zxf 的大作中提到: 】
: 别无他法。
: 【 在 yellowChange (yellowChange) 的大作中提到: 】
: : 三个数组 每个数组m个数(没按大小排序)
: ....................
--
FROM 221.216.116.*
暴力O(m^2)满足要求吗?
【 在 yellowChange (yellowChange) 的大作中提到: 】
: 标 题: 问个算法题
: 发信站: 水木社区 (Fri Sep 17 12:26:49 2021), 站内
:
: 三个数组 每个数组m个数(没按大小排序)
: 要求从三个数组中找出m个数的和的最大值,每个数组可以取0到m个数,但必须是该数组的前几个数连续取
: 怎么做,不用暴力解法的话
: ※ 修改:·yellowChange 于 Sep 17 17:03:05 2021 修改本文·[FROM: 114.253.76.*]
: ※ 来源:·最水木 客户端·[FROM: 114.253.76.*]
--
修改:yellowChange FROM 114.253.76.*
FROM 76.126.252.*
感觉像个动态规划算法,要用一个数组记住1个最大,两个数最大,三个数最大,。。。。。。
【 在 yellowChange 的大作中提到: 】
: 三个数组 每个数组m个数(没按大小排序)
: 要求从三个数组中找出m个数的和的最大值,每个数组可以取0到m个数,但必须是该数组的前几个数连续取
怎么做,不用暴力解法的话
--
FROM 42.198.87.*
空间换时间呢?把数全放大顶堆,取前m个,或者直接三个数组排个序。
【 在 yellowChange 的大作中提到: 】
: 三个数组 每个数组m个数(没按大小排序)
: 要求从三个数组中找出m个数的和的最大值,每个数组可以取0到m个数,但必须是该数组的前几个数连续取
: 怎么做,不用暴力解法的话
- 来自「最水木 for iPhone13,1」
--
FROM 129.227.142.*
人家说了连续的数,你这直接乱序了
【 在 crazycvt (crazycvt) 的大作中提到: 】
: 标 题: Re: 问个算法题
: 发信站: 水木社区 (Fri Sep 24 10:41:20 2021), 站内
:
: 空间换时间呢?把数全放大顶堆,取前m个,或者直接三个数组排个序。
: 【 在 yellowChange 的大作中提到: 】
: : 三个数组 每个数组m个数(没按大小排序)
: : 要求从三个数组中找出m个数的和的最大值,每个数组可以取0到m个数,但必须是该数组的前几个数连续取
: : 怎么做,不用暴力解法的话
:
: - 来自「最水木 for iPhone13,1」
: --
:
: ※ 来源:·最水木 客户端·[FROM: 129.227.142.*]
--
FROM 76.126.252.*
没啊,三个数组依次连续取,放大顶堆。 他那估计是个队列,不支持随机索引,只支持普通便利。
【 在 here080 的大作中提到: 】
: 人家说了连续的数,你这直接乱序了
: 【 在 crazycvt (crazycvt) 的大作中提到: 】
: : 标 题: Re: 问个算法题
: ....................
- 来自「最水木 for iPhone13,1」
--
FROM 202.108.14.*
要不你上个代码?
【 在 crazycvt (crazycvt) 的大作中提到: 】
: 标 题: Re: 问个算法题
: 发信站: 水木社区 (Fri Sep 24 11:39:10 2021), 站内
:
: 没啊,三个数组依次连续取,放大顶堆。 他那估计是个队列,不支持随机索引,只支持普通便利。
: 【 在 here080 的大作中提到: 】
: : 人家说了连续的数,你这直接乱序了
: : 【 在 crazycvt (crazycvt) 的大作中提到: 】
: : : 标 题: Re: 问个算法题
: : ....................
:
: - 来自「最水木 for iPhone13,1」
: --
:
: ※ 来源:·最水木 客户端·[FROM: 202.108.14.*]
--
FROM 76.126.252.*
确定。
你这里的数组没有按大小排序,可以认定每一项均独立。
因此前k项和S(k)构成的数组也是每一项均独立。
所以问题就转变为怎样确定k1+k2+k3=m,使得S(k1)+S(k2)+S(k3)最大。
这个问题应该只能穷举。
【 在 yellowChange (yellowChange) 的大作中提到: 】
: 确定?
--
FROM 49.74.84.*