c - Longest Common Subsequence for Multiple Sequences

Question

I have done a bunch of research for finding the longest for M = 2 sequences, but I am trying to figure out how to do it for M ≥ 2 sequences

I am being given N and M: M sequences, with N unique elements. N is the set of {1 - N}. I have thought about the dynamic programming approach, but I am still confused as to how to actually incorporate it.

Example input

5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4

The max sequence here can be seen to be

5 3 1

Expected output

Length = 3

Answer 1

A simple idea.

For each number i between 1 and N, calculate the longest subsequence where the last number is i. (Let's call it a[i])

To do that, we'll iterate over numbers i in the first sequence from start to end. If a[i] > 1, then there's number j such that in each sequence it comes before i.
Now we can just check all possible values of j and (if previous condition holds) do a[i] = max(a[i], a[j] + 1).

As the last bit, because j comes before i in first sequence, it means a[j] is already calculated.

for each i in first_sequence
    // for the OP's example, 'i' would take values [5, 3, 4, 1, 2], in this order
    a[i] = 1;
    for each j in 1..N
        if j is before i in each sequence
            a[i] = max(a[i], a[j] + 1)
        end
    end
end

It's O(N^2*M), if you calculate matrix of positions beforehand.