# A simplified/harder 2-sequence longest common sub-sequence (LCS) problem

Basically, its a 2-sequence longest common sub-sequence (LCS) problem.

What's so special?

1: each alphabet only occurs 2 times, one in each sequence, which means with no same alphabet in one sequence.

2: we can execute 2 (or k) "LCS"es at a time, and we want the sum length of the 2 "LCS"es is the maximum.

Take the figure in the link for example.

1: when with only 1 LCS, we would run as 1-2-3-4-5-6, which length is 6.

2: but now, we have 2 LCSes, we can run one as 1-2-3-4-8, the other as 7-5-6, so the sum length is 5+3=8. Clearly, it is the optimal (maximum) in this example.

How can I do this? With multiple LCSes, and want to maximum the sum length of these LCSes?

Is this problem a NP-complete?

Thanks so much!

~~A~~B~~C~~D~~E~~F~~G~~H

A..1............................................

B........2......................................

D.................... 3.........................

E...........................4...................

H.............................................. 8

C..............7................................

F...................................5...........

G........................................6......

![LCS figure][1]

http://img2.ph.126.net/gWr2LnyNTpLmTuqjbRwrcw==/6597825131144291222.jpg

-
What's the linked image for? – Tom Leinster Sep 1 '12 at 13:48

If one sequence is $(a_1,\ldots, a_n)$ with all $a_i$ distinct, then the other one is a permutation of it of the form $(a_{w(1)},\ldots, a_{w(n)})$. A common subsequence corresponds therefore to an increasing subsequence of the permutation $(w(1),\ldots,w(n))$.
Now the maximal total length of $k$ disjoint increasing subsequences of a permutation $w$ is given by the sum of the first $k$ parts in the shape associated to $w$ by the Schensted correspondence (this is Greene’s theorem), so this is easy to determine. I suppose there are also efficient algorithms to compute some optimal set of increasing subsequences.