如何找到具有最大总和的递增子序列？

Question

如何找到具有最大总和的递增子序列？

algorithmdynamic-programming

5

如何找到具有最大总和的递增数字子序列。我找到了O(N^2)的方法，但我想知道O(N log N)的方法。

谢谢！

- Elmi Ahmadov

2

重复问题：https://dev59.com/onE85IYBdhLWcg3wvGOm - payne

1

那个重复的问题页面有一个链接指向O(n log n)算法，链接在这里：http://en.wikipedia.org/wiki/Longest_increasing_subsequence - payne

1

为什么这是重复的？最大和的最长递增序列！= 最长递增序列。或者我错过了什么？ - Aryabhatta

@Moron - 据我所见，这甚至不必是最长的。 - IVlad

@IVlad：是的，我试图找到一种简单的方法，而不是找到Andrea的声明的一个真正的反例 :-)（你做到了 :-)) 我相当确定从任何LIS中删除正数的声明需要证明...无论如何... - Aryabhatta

显示剩余9条评论

4个回答

1

扫描数组。维护一个伸展树，将每个元素x映射到以x结尾的子序列的最大和。该伸展树由x（而非x的索引）进行排序，并且每个节点都带有子树的最大值。初始树仅包含一个哨兵Infinity => 0。要处理新值y，请在树中搜索最左侧的值z，使得y <= z。将z旋转到根。 z的左孩子的子树最大值M是y可以延伸的最大子序列和。将(y，M + y)插入树中。最后，返回树的最大值。

- userOVER9000

0

我在Codeforces上遇到了一个类似的问题。这个问题可以使用带有坐标压缩的线段树或平衡二叉搜索树来解决。请参考下面的链接以获取详细说明。

最大和递增序列

阅读完后，您可以尝试在Codeforces上解决this问题。

- Shivam Mitra

0

1.) 对子序列进行排序

2.) 遍历您的列表，将下一个元素添加到前一个元素

3.) 一旦您达到两个元素的总和大于maximum_sum，请停止。之前的所有内容都可以结合在一起，<= maximum_sum。

这假设您要添加两个元素以使maximum_sum。一般概念可推广为0-N求和，其中N是“数字”的长度。但是，您没有明确说明要添加什么，因此我做了一个假设。另外，我不确定这是否会给您最长的数字子序列，但它将在N log N中为您提供数字子序列。

这是亚马逊公司在我第一轮面试时问我的问题，当时我因食物中毒而呕吐。我通过了第二轮面试，但他们似乎不想超越那一点。希望如果这是一个面试问题，您能做得比我更好，所以我的答案可能不是最好的，但希望它比说您有重复要好...

希望这有所帮助，

-Brian J. Stinar-

- Brian Stinar

1

我不懂。这要求最大的递增子序列。排序如何确保您得到一个有效的子序列？ - IVlad

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hugomg · Accepted Answer

我假设：

您完全不关心子序列的长度。
子序列不需要连续。

这会产生很大的差异！

解决方案

令数组 A 的最优递增子序列（IS）集合 S 为一组 IS，使得在 A 中的每个 IS s，我们恰好有以下情况之一：

s 在 S 中
存在一个 IS s' 在 S 中，满足
- sum(s') >= sum(s)，并且
- largest_element(s') <= largest_element(s)

最优集合 S 可以按照子序列的最大元素和它们的总和进行排序 - 应该是相同的顺序。这就是我所说的稍后要讨论的最小/最大序列。

然后，我们的算法必须找到 A 的最优集合，并返回其最大序列。S 可以通过以下方式计算：

S := {[]} //Contains the empty subsequence
for each element x in A:
   s_less := (largest sequence in S that ends in less than x)
   s := Append x to s_less
   s_more := (smallest sequence in S that has sum greater than s)

   Remove all subsequences in S that are between s_less and s_more 
    (they are made obsolete by 's')

   Add s to S

在S中最大的子序列是数组中的最大子序列。

如果S是平衡二叉树，则每个步骤可以以O(log n)实现。n个步骤总共需要O(n*log n)的复杂度。

注意：我的伪代码中可能会有一些+-1的错误-找出它们留给读者作为练习 :)

具体例子如下：最右侧的子序列始终是到目前为止最好的，但其他子序列也很重要，因为它们在未来可能会成为最重的序列。

curr array | Optimal Subsequences
[]              []

//best this we can do with 8 is a simgleton sequence:
[8]             [] [8]

//The heaviest sequence we can make ending with 12 is [8,12] for a total of 20
//We still keep the [8] because a couble of 9s and 10s might make it better tahn 8+12
[8,12]          [] [8] [8,12]

[8,12,11]       [] [8] [8,11] [8,12]
[8,12,11,9]     [] [8] [8,9] [8,11] [8,12]

//[8,9,10] makes [8,11] and [8,12] obsolete (remove those).
//It not only is heavier but the last number is smaller.
[8,12,11,9,10]  [] [8] [8,9] [8,9,10]