如何为给定数组生成 k 个最大子集和（包含正数和负数）
How to generate k largest subset sums for a given array (contains positive and negative numbers)
所以问题很简单，给定一个大小为 N( N<=10^5) 的数组，我们想要生成 k 个最大子集和，其中 k 在最坏情况下是 (2000 和 2^N) 的最小值).
我们要按降序输出
有没有办法以低于指数级的复杂度来做到这一点。
我的想法是
如果我们必须生成 2^N 项，复杂度怎么可能小于 2^N,
在amazon OA中提问（问题叫做find k maximum priority）
我只是概述一下。由您来实现它并证明它有效。
首先，我们一次性找到正数的总和。这是最大金额。我们用 [maximum_sum].
初始化我们的答案数组
接下来，我们创建一个绝对值数组 av，从小到大排序。
接下来，我们创建一个优先级队列upcoming。它将从一对开始。那对将是 (maximum_sum - av[0], 0)。这些对按字典顺序与最大总和进行比较。
在 answer 中有足够的元素之前，我们将：
get (next_sum, i) from upcoming
add next_sum to answer
if i < N:
add (next_sum + av[i] - av[i+1], i+1) to upcoming
add (next_sum - av[i+1], i+1) to upcoming
此算法将占用 O(N+k) 内存和 O(N log(N) + k log(k)) 工作来生成前 k 个答案。它取决于 N 和 k 但两者都不是指数的。
所以问题很简单，给定一个大小为 N( N<=10^5) 的数组，我们想要生成 k 个最大子集和，其中 k 在最坏情况下是 (2000 和 2^N) 的最小值).
我们要按降序输出
有没有办法以低于指数级的复杂度来做到这一点。 我的想法是 如果我们必须生成 2^N 项，复杂度怎么可能小于 2^N,
在amazon OA中提问（问题叫做find k maximum priority）
我只是概述一下。由您来实现它并证明它有效。
首先，我们一次性找到正数的总和。这是最大金额。我们用 [maximum_sum].
接下来，我们创建一个绝对值数组 av，从小到大排序。
接下来，我们创建一个优先级队列upcoming。它将从一对开始。那对将是 (maximum_sum - av[0], 0)。这些对按字典顺序与最大总和进行比较。
在 answer 中有足够的元素之前，我们将：
get (next_sum, i) from upcoming
add next_sum to answer
if i < N:
add (next_sum + av[i] - av[i+1], i+1) to upcoming
add (next_sum - av[i+1], i+1) to upcoming
此算法将占用 O(N+k) 内存和 O(N log(N) + k log(k)) 工作来生成前 k 个答案。它取决于 N 和 k 但两者都不是指数的。