最長増加部分列 Longest Increasing Subsequence

東西に並んだ高さの異なるｎ本の木があります。あるキコリがこれらの木を、西から東の方向へ木の高さが小さい順に並ぶように、いくつかの木を切り倒すことにしました。木の数を最大にするにはどの木を切れ（残せ）ばようでしょうか？

このような単純な（くだらない）問題でも、考えられる組み合わせを全て調べようとすると、それは各木を選ぶか選ばないかの組み合わせになるので、計算量はO(2ⁿ)となってしまいます。

この問題は、与えられた数列の最長増加部分列 Longest Increasing Subsequence (LIS) を求めることに帰着します。

最長増加部分列とは、与えられた数列 S

S = a₁, a₂ , , , a_n

の増加部分列　（ すべてのi, j (i < j)について a_i < a_j を満たす部分列 ）
の中で長さが最大のものをいいます。

例えば、

S = 4 1 6 2 8 5 7 3

の増加部分列には

4 8
1 6 8
4 6 7
1 6 7
.
.

などがありますが、長さが最大のものは

1 2 5 7

です。

動的計画法によって与えられた数列の最長増加部分列をみつけることができます。
ここでは、n を数列の長さとすれば O(n²) の効率のアルゴリズムを紹介します。

与えられた数列を T とし、インデックスが 1 から始まるとします。また
L を、L[i] が「T[1]からT[i]までの要素でT[i]を最後に選んだときの LIS の長さ」を示す配列とします。

L[0] を 0 に初期化します。また T[0] は 0 （通常は非常に小さい値）に初期化します。

index	0	1	2	3	4	5	6	7	8
T	0	4	1	6	2	8	5	7	3
L	0

以下 L[i] ( i が 1 から n まで)を計算します。

L[i] の計算：
j が 0 から i - 1 について、T[j] < T[i] を満たしかつ L[j] が最大である j を k とすると
L[i] = L[k] + 1 とします。

以下、計算の流れです。

index	0	1	2	3	4	5	6	7	8
T	0	4	1	6	2	8	5	7	3
L	0	1

index	0	1	2	3	4	5	6	7	8
T	0	4	1	6	2	8	5	7	3
L	0	1	1

index	0	1	2	3	4	5	6	7	8
T	0	4	1	6	2	8	5	7	3
L	0	1	1	2

index	0	1	2	3	4	5	6	7	8
T	0	4	1	6	2	8	5	7	3
L	0	1	1	2	2

index	0	1	2	3	4	5	6	7	8
T	0	4	1	6	2	8	5	7	3
L	0	1	1	2	2	3

index	0	1	2	3	4	5	6	7	8
T	0	4	1	6	2	8	5	7	3
L	0	1	1	2	2	3	3

index	0	1	2	3	4	5	6	7	8
T	0	4	1	6	2	8	5	7	3
L	0	1	1	2	2	3	3	4

index	0	1	2	3	4	5	6	7	8
T	0	4	1	6	2	8	5	7	3
L	0	1	1	2	2	3	3	4	3

L の要素で最大のものが、与えられた数列の LIS となります。

また、実際のＬＩＳを求めるためには、
P を P[i] が「T[1]からT[i]までの要素でT[i]を最後に選んだときのLISの１つ前の要素のインデックス」を示す配列とし、
各 L[i] を計算するときに、
P[i] = k
とすれば P の要素を辿ることで実際の LIS を求めることができます。
例えば、上記の例で P は以下のようになるので、

index	0	1	2	3	4	5	6	7	8
T	0	4	1	6	2	8	5	7	3
L	0	1	1	2	2	3	3	4	3
P	-1	0	0	1	2	2	4	6	4

p = 7 (LIS の最後のインデックス)
p = P[p] = P[7] = 6
p = P[p] = P[6] = 4
p = P[p] = P[4] = 2
よって、インデックスの列が 2 4 6 7 なので対応する LIS は
1 2 5 7
となります。

001 #include<iostream>
002 #define MAX 2000
003 using namespace std;
004 
005 int size, length;
006 int T[MAX+1], L[MAX+1], P[MAX+1];
007 
008 void printLIS(int i){
009     if ( P[i] == -1 ) return;
010     printLIS(P[i]);
011     cout << T[i] << endl;
012 }
013 
014 int LIS(){
015     T[0] = 0;
016     L[0] = 0;
017     P[0] = -1;
018     for ( int i = 1; i <= size; i++ ){
019         int k = 0; // max index
020         for ( int j = 0; j <= i - 1; j++ ){
021             if ( T[j] < T[i] && L[j] > L[k] ){
022                 k = j;
023             }
024         }
025         L[i] = L[k] + 1;
026         P[i] = k;
027     }
028     
029     // print result
030     int maxv = 0;
031     int maxi;
032     for ( int i = 1; i <= size; i++ ){
033         if ( maxv <= L[i] ){
034             maxv = L[i];
035             maxi = i;
036         }
037     }
038     
039     cout << maxv << endl;
040     cout << "-" << endl;
041     printLIS(maxi);
042 }
043 
044 main(){
045     cin >> size;
046     for ( int i = 1; i <= size; i++ ) cin >> T[i];
047     LIS();
048 }