Explain the algorithm to solve 'longest increasing subsequence' problem

Question

I have been trying to understand this algorithm for past two hours, but can't seem to get it. Can someone please explain it in easy to understand manner?

function lis_length(a)
    n := a.length
    q := new Array(n)
    for k from 0 to n:
        max := 0;
        for j from 0 to k, if a[k] > a[j]:
            if q[j] > max, then set max = q[j].
        q[k] := max + 1;
    max := 0
    for i from 0 to n:
        if q[i] > max, then set max = q[i].
    return max;

Henriques

Walk through the code with a ten-element array on pencil and paper. Or go back to the documentation for the function. – Garton

^ @RaymondChen This is so unhelpful. It would be better to just not post anything than give a suggestion like this. It detracts from the answer quality on this site, which does nothing but harm the community and by extension yourself. – Household

Answer 1

After the first (double) loop terminates, q[i] is the length of the longest increasing subsequence ending at position i.

To see how the double loop works, suppose q[j] already contained the length of the largest increasing subsequence ending at position j, but only for j between 0 and k-1. Given this, how would you compute q[k]?

Well, you would find all of the j with j < k and a[j] < a[k], see which of the corresponding q[j] values was biggest, add one, and stash that value in q[k]. This is exactly what the inner loop does.

So at entry to the inner loop, q[j] already has the correct values for j between 0 and k-1. And at exit, it also has the correct value for k. So by the time the double loop exits, q[i] has the correct value for all i between 0 and n.

The final loop just selects the largest of those, which is the answer.

Twum

Answer 2

For each element set the count of longest subsequence of elements made with current element as incremented by one length of longest subsequence of elements preceding current element such that their largest value is smaller than the value of current element.

The algorithm takes array of positive numbers (can't have zero or less as element).

Etherealize