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>



A simplified/harder 2-sequence longest common sub-sequence (LCS) problem 
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.


