给定一个整数数组和一个阈值，确定数组中小于或等于阈值的任何子序列的最大总和。对于除最多 15 个元素之外的所有元素，array[i] >= 2*array[j] 或 array[j] >=2*array[i]其中 j!=i。
threshold最大可达10^17，数组长度最大可达60，并且array[i]最多可达 10^16。
这里的threshold太高了，无法用普通的背包方法解决。我尝试将这个数组分成三个部分，然后通过回溯通过蛮力获取可能的总和列表，然后合并三个列表以找到结果。但我认为可能有更优化的方式来做到这一点。
最佳答案
此问题经过精心设计，因此所有常用方法都会耗尽空间。你必须使用提示。
第 1 步，对数组大小进行降序排序，然后将其分成最多 15 个“奇怪的”和一个元素链，这样 b1 >= 2*b2, b2 > = 2*b3 等等。
为此，您可以将最大的放入链中，然后将奇怪的放入奇怪的数组中，直到找到大小的一半，将其添加到链中，将奇怪的放入奇怪的数组中，依此类推。
现在，对于最多 32768 个怪异子集的每个子集，请尝试找出其余子集中的哪个子集最接近您。但是，您可以使用以下观察。对于您可以选择包含的任何元素，要么太大而无法包含，要么必须包含。 (因为如果你不包括它，那么所有其他的加在一起会给你一个较小的数字。)这给你最多 45 个决策点来考虑。
换句话说
for each subset of weird ones:
for each element of the chain
If we can add this element:
Add it to the set we are looking at
if sum(this set) is best so far, improve our max
return the best found.
关于algorithm - 最大序列和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58594660/