最大序列和

Question

给定一个整数数组和一个阈值，确定数组中小于或等于阈值的任何子序列的最大和。对于除最多 15 个元素之外的所有元素，array[i] >= 2*array[j] 或 array[j] >=2*array[i] 其中 j!=i.

threshold最大可达10^17，数组长度最大可达60，array[i]最大可达10^16。

这里threshold太高了，不能用正常的背包法解决。我尝试将这个数组分成三个部分，然后通过回溯通过蛮力获取可能的总和列表，然后合并三个列表以找到结果。但我认为可能有更好的方法来做到这一点。

Answer 1

这个问题已经过精心设置，因此所有常用方法都将运行排除在 space 之外。你必须使用提示。

第1步，将数组大小降序排列，然后将其分成最多15个"weird ones"和一串元素，例如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.

最大序列和

Maximum Subsequence Sum

algorithm

knapsack-problem

data-structures