algorithm - 是否有可能以降序迭代获取数组的部分和？

我们有一个排序数组，比方说
30，20，10，-1，-2，-15
现在我们要计算它的部分和（对于每个数字，您可以选择是否添加它），并按降序取前n个最大的数字（比如，前11个）。

60 = 30 + 20 + 10
59 = 30 + 20 + 10 -1
58 = 30 + 20 + 10    -2
57 = 30 + 20 + 10 -1 -2
50 = 30 + 20
49 = 30 + 20      -1
48 = 30 + 20         -2
47 = 30 + 20      -1 -2
45 = 30 + 20 + 10       -15
44 = 30 + 20 + 10 -1    -15
43 = 30 + 20 + 10    -2 -15

一个简单的解决方案是计算所有组合（例如，上面有2^6=64个组合），按降序排序，然后获取其中的前11个数字：
60、59、58、57、50、49、48、47、45、44、43、42、40、39、38、37、35、34、33、32、30、30、29、29、28、28、27、27、25、24、23、22、20、19、18、17、15、15、14、14、13、13、12、12、10、9、8、7、5、4、3、2、0、-1、-2、-3、-5、-6、-7、-8、-15、-16、-17、-18
然而，当数组的长度较大时，计算所有的组合是不可行的所以问题是，是否有可能以迭代的方式获取前n个最大的部分和，例如一次获取一个数字？
编辑
明确地说，最终目标是，假设数组是全局的，我想要一个函数f()：通过迭代调用f()，它以降序返回最大的部分和
call f（），返回60
再次调用f（），返回59
再次调用f（），返回58
……

最佳答案

对于这类问题，有一个非常一般的过程叫做Lawler-Murty，在http://www.vldb.org/pvldb/vol4/p1028-golenberg.pdf中描述当你不想要所有的答案时，这是最实际的，也许仅仅是前十名，或者足够耗尽一个人浏览搜索结果的耐心。
以下是针对您的问题提供更简单版本的尝试。
把每个答案看作是由一个比特向量定义的，其中0表示选择较低的选项，1表示选择较高的选项。即：如果数字为正，则1表示已选择，0表示未选择如果为负数，则1表示未选择，0表示已选择所以111111表示30+20+10（+0+0+0），000000表示（0+0+0）-1-2-15。111111永远是最高的答案。
把这些向量想象成一棵树，上面有111111个通过设置最左边的0位，可以找到任何0位向量的父向量。这意味着父对象的值总是高于其子对象的值节点具有可变数量的子节点，其中111111具有最多的子节点：011111、101111、110111、111011、111101和111110。枚举父级的所有子级的一种方法是将父级中所有左边没有0位的1取出来，然后依次清除。
树顶是111111把这个放在一个优先级队列中，按照从每个向量计算出的和的顺序排列。现在，重复地以最高的总和将项目从队列中取出，打印出来，并将其所有子项放入队列中。
这将按和的非递增顺序打印出所有答案最大值的儿童不高于父级，因此优先级队列中的最大值永远不会增加。每一个可能的答案都有一个父链，其前导到111111（设置最左边的位），因此您可以找到每一个可能的答案。

关于algorithm - 是否有可能以降序迭代获取数组的部分和？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53245932/