Talk:Longest increasing subsequence

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)

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.

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)

I absolutelly agree. There is no description or explanation here. The code is basicly patience sort, which again is the use of some basic math theorems from combinatorics.

Description does everything to hide the fact it is patience sort, and avoids mentioning these math theorem.

Its really nice to avoid math and all that, until one actually have to prove or understand correctnes of the algorithm. Alogorithm without proof is useless, and I cant recall where the proof of this algorithm is. Testing on some cases, does not prove or convice correctnes.

The normal reader in programming and computer science, actually think theorem/lemma and not these unit testing thingy when it comes to algorithms. Correctness of algorithm and correctness of implementation of algorithm is totally two different things, and therfore one should really add a source to what is written (to help people find further details) 2001:2020:307:CBAE:F1C7:F7AC:F293:6F34 (talk) 07:22, 21 August 2023 (UTC)

The animated GIF labeled "Demo of the code" is confusing.

There could be code for a similar algorithm that appears that way. However, it isn't actually a demo of the code presented because it presents actual subsequences of the X[i] whereas the pseudo-code is dealing in index values M[j] and P[j]. Indeed, subtleties about the P[j] disappear completely, so the construction of the sequence at the end of the code is not even present. (Indeed the data it requires cannot even be inferred from the GIF.) Furthermore, the 'demo' seems to imply a storage requirement that is O(N^2), whereas, for the code, it is only O(N). I think there should at least be a comment somewhere to the effect that what the GIF presents are the actual complete subsequences for each length, as opposed to what the code really maintains, namely the indices for the last two elements of each such subsequence. DrHow (talk) 21:27, 11 August 2020 (UTC)

Also, the GIF goes way too fast to be understood by someone new to the algorithm. — Preceding unsigned comment added by 24.226.205.62 (talk) 17:26, 7 March 2021 (UTC)

Output Sensitivity

Let us suppose that output of the algorithm is of length k. Strictly speaking, the complexity of algo is O(n log k). We should discuss this output sensitivity in the article to explain the subtleties of the algo. What do you people say ?? —Preceding unsigned comment added by Msjaiswal (talk • contribs) 22:11, 29 November 2010 (UTC)

I agree. To be more accurate, the page should mention the complexity as O(n log k) and not O(n log n). 117.211.88.150 (talk) 22:28, 6 July 2011 (UTC)

Example, please

To be truly useful, this article needs a concrete example. -- 172.191.26.146 (talk) 17:35, 26 February 2009 (UTC)

I second this. A concrete example is necessary to explain the O(nlogn) algorithm. —Preceding unsigned comment added by 24.6.228.39 (talk) 23:41, 25 October 2009 (UTC)

Binary search?

Could somebody pls explain how the binary search works? X is not sorted, so I am not sure how to use binary search on it.--Jirka6 (talk) 18:29, 21 April 2009 (UTC)

As the article states, the sequence X[M[1]], X[M[2]], ..., X[M[L]] is sorted. —David Eppstein (talk) 20:14, 21 April 2009 (UTC)

If X is sorted, then the largest nondecreasing sequence in X is X itself. The nontrivial problem is to find the largest non-decreasing sequence in an unsorted sequence. I suggest that the nlogn solution be removed unless it's validity can be verified by someone smarter than myself. —Preceding unsigned comment added by 74.13.119.105 (talk) 05:02, 7 November 2009 (UTC)

X[1], X[2], X[3], ... is not sorted. X[M[1]], X[M[2]], X[M[3]], ... is a sorted subsequence. The binary search is in the sorted subsequence, not in the whole sequence. —David Eppstein (talk) 05:12, 7 November 2009 (UTC)

I don't understand, David. See this example (provided in the page). I repeat every array in the form (index, value) for the reader's convenience.

X = [0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15]

X = [(0, 0) (1, 8) (2, 4) (3, 12) (4, 2) (5, 10) (6, 6) (7, 14) (8, 1) (9, 9) (10, 5) (11, 13) (12, 3) (13, 11) (14, 7) (15, 15)]

M = [-1 0 1 3 7 11 15]

M = [(0, -1) (1, 0) (2, 1) (3, 3) (4, 7) (5, 11) (6, 15)]

The meaning of M - as I understand it - is:

The longest increasing subsequence of length 0 is encountered for the first time at position -1 (i.e. it doesn't exist)

The longest increasing subsequence of length 1 is encountered for the first time at position 0 ([0])

The longest increasing subsequence of length 2 is encountered for the first time at position 1 ([0 8])

The longest increasing subsequence of length 3 is encountered for the first time at position 3 ([0 8 12], among others)

The longest increasing subsequence of length 4 is encountered for the first time at position 7 ([0 8 12 14], among others)

The longest increasing subsequence of length 5 is encountered for the first time at position 11 ([0 2 6 9 13], among others)

The longest increasing subsequence of length 6 is encountered for the first time at position 15 ([0 2 6 9 13 15], among others)

X[M] = [-1 0 8 12 14 13 15]

The last one is not sorted, which contradicts your claim. Is there something I'm missing here? --213.210.194.114 (talk) 07:39, 8 March 2012 (UTC)

Well there's your problem. M[i] is not the position of the end of the *first* subsequence of length i. It is the position of the end of the subsequence of length i that has the smallest possible end value. —David Eppstein (talk) 07:46, 8 March 2012 (UTC)

Thank you, David! Now I understand it. I've implemented it and it's getting the correct values. For those who want to practice implementing it, try solving this problem. --213.210.194.114 (talk) 10:06, 8 March 2012 (UTC)

More useful information required

Yes, I also think the algorithm should be outlined, as well as a word about the asymptotic performance (It is in the order of 2Sqrt(n) for random sequences of length n). Also, the corresponding online problem is equally important for applications(online monotone subsequence problem means that the monotone sequence must be selected on sequential observation without recall on preceding numbers) Optimal rules for the sequential selection of monotone subsequences of maximum expected length yield, interestingly, still asymptotically in expectation Sqrt(2n). 81.247.74.101 (talk) 19:55, 18 May 2009 (UTC)

Does the Pseudo-code even work?

So far as I can tell, the psuedo-code algorithm as it is currently written does not work. It requires the value of M[J+1] for a comparison on the first loop, but M will only have a size of 1 at this time. Also, what goes in P[0] (nothing so far as I can tell, so why not store P[i-1]?)? —Preceding unsigned comment added by Clhodapp (talk • contribs) 22:39, 5 November 2009 (UTC)

Yes, the pseudocode works. Here is a Python implementation following it exactly. —David Eppstein (talk) 05:50, 7 November 2009 (UTC)

Impossible to say. One can unit test it, and increse probability that it can work.

However, in programming competition; there is always some cases where something goes wrong. Its better

to make sure to bullet prove correctnes, before implementing anything.

There is no proof here, and everything in the section goes under "Original research".

Anyone can just remove the section with reason "Original unrefrenced uncomprehensable research", where people

who undo this risk being permantly blocked out from wikipeida. 2001:2020:307:CBAE:F1C7:F7AC:F293:6F34 (talk) 07:58, 21 August 2023 (UTC)

import unittest

def LongestIncreasingSubsequence(X):
    """
    Find and return longest increasing subsequence of S.
    If multiple increasing subsequences exist, the one that ends
    with the smallest value is preferred, and if multiple
    occurrences of that value can end the sequence, then the
    earliest occurrence is preferred.
    """
    n = len(X)
    X = [None] + X  # Pad sequence so that it starts at X[1]
    M = [None]*(n+1)  # Allocate arrays for M and P
    P = [None]*(n+1)
    L = 0
    for i in range(1,n+1):
        if L == 0 or X[M[1]] >= X[i]:
            # there is no j s.t. X[M[j]] < X[i]]
            j = 0
        else:
            # binary search for the largest j s.t. X[M[j]] < X[i]]
            lo = 1      # largest value known to be <= j
            hi = L+1    # smallest value known to be > j
            while lo < hi - 1:
                mid = (lo + hi)//2
                if X[M[mid]] < X[i]:
                    lo = mid
                else:
                    hi = mid
            j = lo

        P[i] = M[j]
        if j == L or X[i] < X[M[j+1]]:
            M[j+1] = i
            L = max(L,j+1)
    
    # Backtrack to find the optimal sequence in reverse order
    output = []
    pos = M[L]
    while L > 0:
        output.append(X[pos])
        pos = P[pos]
        L -= 1
        
    output.reverse()
    return output

# Try small lists and check that the correct subsequences are generated.

class LISTest(unittest.TestCase):
    def testLIS(self):
        self.assertEqual(LongestIncreasingSubsequence([]),[])
        self.assertEqual(LongestIncreasingSubsequence(range(10,0,-1)),[1])
        self.assertEqual(LongestIncreasingSubsequence(range(10)),range(10))
        self.assertEqual(LongestIncreasingSubsequence(\
            [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]), [1,2,3,5,8,9])

unittest.main()

Pseudo-code

The pseudo-code mixes up array index numbering. For instance, it declares M to be from M[1], M[2] etc., but inside the program it starts zero-indexing with j=0. Somebody should fix this. Andares (talk)

Go ahead, be bold! Fix the problem! :) See: WP:SOFIXIT Jwesley₇₈ 18:25, 5 April 2010 (UTC)

Explain the P[] Array

It says that P is the predecessor of X. Can someone explain this more fully? — Preceding unsigned comment added by 96.236.148.28 (talk) 16:12, 27 October 2011 (UTC)

Code is basicly patience sort, and description has nothing to do with code

Code is basicly patience sort, and description has nothing to do with code

I suspect fraud against wikipedia users, on this ground.

I ask wikipedia administrator to check and fix this. — Preceding unsigned comment added by 2001:2020:331:F0DB:599D:553D:4E8F:5A1A (talk) 17:31, 20 August 2023 (UTC)

Bad structure and bad approach to just talk about "best" algorithm

Article is really bad, because its focus on personal opinion of "best" algorithm.

This is unwanted approach from wikipedia point of view. One should instead give a overview over different approaches; what is done before, to make it easier for others to get a overview over the subject. Different appraoches is many: pasience sort, segment tree, and dynamic programing. Each of these algorithms has strength and weaknesses, and one should not rule out them due to rapid changes in computer architectures and waste range of different computer architectures.

Most of structure in article is bad, and should be fixed. Young tabular should be explained in context of patience sort, and not out of context, because it can be used to give insight to patience sort. — Preceding unsigned comment added by 2001:2020:307:CBAE:7462:DCE2:86F7:818D (talk) 17:42, 21 August 2023 (UTC)