Talk:Longest increasing subsequence problem

From Wikipedia, the free encyclopedia

[edit] Request

could someone who knows this topic add more on the O(nlgn) solution please

See the patience sorting if you want one, but beware that it requires TOTAL ordering of the sequence (as opposed to the general graph-style weak ordering). BTW, this article needs to be improved to clearly separate the two cases. --BACbKA 17:51, 12 May 2006 (UTC)

[edit] Dynamic Programming Comment

"Though this is asymptotically equivalent to the longest-common subsequence version of the solution, the constant is lower, as there is less overhead."

Yeah, but I don't think the memory overhead is asymptotically equivalent. If you have confidence that I'm right, please edit in a comment to that effect. 128.113.96.109 18:28, 31 March 2006 (UTC)

you cant use asymptotic analysis and talk about constants.. it makes no sense for the same reason as why we don't consider constants while analysing algorithms in this way.

[edit] Pseudo-code could be easier to understand

After reading the algorithm in this page, I followed the external link to the Algorithmist page. At that time, the algorithm written here was not very clear to me yet. However, I found the pseudo-code in the Algorithmist's page very easy to understand, and at that point I could easily understand the enhancement that was done in the code in this page.

Maybe listing both codes on this page would make it easier for people to understand the main algorithm, and how it was enhanced.

Thanks. --Hosam Aly 20:09, 7 January 2007 (UTC)

It is not so much a question of an algorithm being enhanced. They are two quite different algorithms. The one on the Algorithmist is much less efficient despite its simplicity. But if you want an in-WP link to pseudocode for a similarly simple but inefficient algorithm, follow the links from the section about computing the longest increasing subsequence using longest common subsequences. —David Eppstein 04:37, 8 January 2007 (UTC)