爲什麼我不能通過對序列進行簡單排序來解決最長的遞增子序列？

http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms說最有效的解決方案是O（n log n），因此如果我排序序列，它將是O（n log n），然後如果我遍歷排序的序列，拒絕每個不是因此該算法將在O（n log n + n）中爲〜O（n log n）...爲什麼我不能通過對序列進行簡單排序來解決最長的遞增子序列？

來源

2014-01-29 user1479589

什麼問題？ – Jatin

*遍歷排序的序列，拒絕不增加的每個項目* - 再次讀取它。這將是完整的序列。你已經對它進行了排序。這並不是真正的算法。 –

[2,3,1]中最長的子序列與[1,2,3]不同。 – Mehrdad

對序列進行排序會改變項目的順序原始序列，並且您的方法將始終返回與原始總序列長度相同的最短序列。 Se Mehrdad的評論。

從你的鏈接：

在二進制範德瓦Corput序列

0，8,4，12，2，10，6，14，1,9，5，13，3，11 ，7，15，...

最長遞增子是現在

0，2，6，9，13，15

讓你的應用algorithim：

排序的原始序列變爲：

0，1，2，3，4，5，6，7，8，9，10，11，12，13，14，15

最長增加這裏subsequnce是：

0，1，2，3，4，5，6，7，8，9，10，11，12，13，14，15

來源

2014-01-29 16:43:29

非常感謝你回答我這個非常愚蠢的想法..我應該用wiki上的結果來測試它..原諒我的天真..但是，你可以請看看： http：// stackoverflow。 com/questions/21435497/knuthmorrispratt-algorithm？noredirect = 1＃comment32342555_21435497 – user1479589

沒有理由道歉。在somone指出他們的假設之後，很容易發現我們的假設存在缺陷。這一切都發生在我身上。 –

另外我會在今天晚上看看這個問題。我在工作，現在沒有時間真正地看那一個。 –

-1

「如果我排序序列」這是爲什麼？當你對它進行排序時，所有子序列會發生什麼？ ;-)

來源

2014-01-29 16:48:23 Kotse

這不是一個真正的答案。 –

是的，應該是一個評論 – Kotse

我現在意識到..對不起.. – user1479589

如果你排序它，那麼你破壞了輸入，並沒有解決真正的問題。

來源

2014-01-30 13:51:46 user239053

爲什麼我不能通過對序列進行簡單排序來解決最長的遞增子序列？

回答

相關問題