如何找到最大數量的遞增子序列？

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問題。