Example: Longest Increasing Sequence - rFronteddu/general_wiki GitHub Wiki

Given a sequence find, the LIS such that all elements are in sorted order.

If we have S = 3, 4, -1, 0, 6, 2, 3

[1, 2, 1, 2, 3, 3, 4]

// S[1..n]
LIS(S)
    n = S.len
    let d[1..n] prev[1..n]
    for i = 1 to n
        prev[i]=-1
   
    for i = 1 to n
        d[i] = 1

    for i = 2 to n
        for j = 1 to i-1
            if S[j] < S[i] && 1 + d[j] > d[i]
                d[i] = 1 + d[j]
                prev[i] = j

    lis = []
    curIndex = maxIndex(d)
    while curIndex != -1
        lis.push(S[curIndex])
        curIndex = prev[curIndex]

    for el : lis
        print(el)

    return maxIndex(d)