如何找到最大数量的递增子序列？

Question

如何找到最大数量的递增子数列。 我发现O（N^2）但我想知道O（N log N）。

谢谢！

Answer 1

1）排序您的序列

2）通过列表迭代，添加下一个元素的前一个元素

3）一旦你达到两个元素谁的概率要比maximum_sum时，停止。以前的所有内容都可以合并为< = maximum_sum。

这假定您要求添加两个元素来创建maximum_sum。一般概念可以推广为0-N总和，其中N是你的“数字”的长度。但是，你没有澄清你实际上加在一起，所以我做了一个假设。此外，我不确定这是否会给你“最长”的数字子序列，但它会给你一个N日志数N的序列号。

这是一个采访问题Amazon.com问我，而我在采访的第一轮中，我从食物中毒中抽出我的胆量。我做了两轮采访，他们似乎并不想在这一点上前进。希望你做的比我，如果这是一个面试问题，所以我的答案可能不是最好的，但我希望它比说你有一个更好的重复好...

希望这有助于，

-Brian J. Stinar-

Answer 2

我假设：

• 你不关心序列长度在所有。
• 子序列不必是连续

这使得世界的差异！

---

解

让一组最优的增加子序列（IS）用于阵列的SA是一组国际空间站的，使得每个IS在As我们有正好一个：

• s in in 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中最大的子序列是在阵列中的最大子序列。

每一步都可以在O（log n）中实现，S是平衡二叉树。 n个步骤给出了O（n * log n）的总复杂度。

警告：可能有很大可能是有些+ - 在我的伪代码1个错误（S） - 找到他们就留给exercize读者:)

---

我会尽力给予具体示例。也许它有助于使这个想法更清晰。 到目前为止，最右边的子序列总是最好的，但其他子序列是因为将来它们可能会成为最重的序列。

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] 

Answer 3

扫描阵列。维持一个splay tree将每个元素x映射到以x结尾的子序列的最大和。此splay树按x排序（不是x的索引），并且每个节点都用子树最大值进行装饰。最初，树只包含一个哨兵Infinity => 0。要处理新的值y，请搜索树的最左边的值z，使得y < = z。将z展示给根。 z的左子树的子树max M是y可以扩展的子序列的最大和。将（y，M + y）插入树中。最后，返回最大树。

Answer 4

我在代码中遇到了类似的问题。该问题可以通过使用带有坐标压缩的分段树或使用平衡二叉搜索树来完成。有关详细说明，请参阅以下链接。

maximum sum increasing sequence

看完之后，你可以尝试在codeforces this问题。