最長増加部分列とは？

数列$A=a_0,a_1,…,a_{n−1}$があるとき，
増加部分列は
$$0≤i_0<i_1<…<i_k<n　\cap \ a_{i0}<a_{i1}<…<a_{ik}$$
を満たす部分列 $a_{i0},a_{i1},…,a_{ik}$で，最長増加部分列はその中で最も$k$が大きいもの．
（上の問題からのコピペです）

$5,3,1,2,3,5,4,8,7,1$のような数列の場合，最長増加部分列は$1,2,3,4,7$となります．

Nが小さいとき

数列の長さ$N$が$N<10^3$程度なら，N個のテーブルをもつDPテーブルを用意して所謂配るDPをしていけば，$O(N^2)$で解けますね．
しかし，$N<10^5$になってくるとTLEしてしまいます．

解法

1.INFで初期化した，文字列の長さN個のテーブルをもつ１次元のDPテーブルを用意
2.列を前から見て行く
3.i番目までで作れる長さjの増加部分列のうち，DP[j]に長さj+1の全ての部分増加文字列の中で最大の数(一番後ろのもの)が最小の部分文字列の最大の数を格納していく
という手順で更新していきます．

これを表にして見ていくとあることが分かるのですが......

$5,3,1,2,3,5,4,8,7,1$を例に見ていきましょう．

縦軸がDPテーブルのインデックス，横軸がカウンタがiのとき見ている値$a_i$です．

ここで，気づく人は気づく特性があり，1回ごとの値$a_i$によるDPテーブルの更新は１つの要素のみです．

そしてこの更新する要素のインデックスは，なんとDPテーブル内を$a_i$で2分探索(lower_bound)で求めることができます．

ここまでの処理は，N回の処理ごとに$O(logN)$の２分探索を行うので，$O(NlogN)$となります．

あとは，DPテーブル内のINFではないインデックスの最大値+1がそのまま，最長増加部分文字列の長さとなるので，INFでlower_boundを取るとすぐに求められますね．

コード

最初に貼った問題も僅か数行で書けます．

#include<bits/stdc++.h>
using namespace std;
#define INF 0x7FFFFFFF

int main(){
    int n;
    cin >> n;
    vector<long long> a(n);
    for(int i=0 ; i < n ; i++) cin >> a[i];
    vector<int> dp(n,INF);
    for(int i = 0; i < n; i++)
        *lower_bound(dp.begin(),dp.end(),a[i]) = a[i];
    cout << lower_bound(dp.begin(),dp.end(),INF) - dp.begin() << endl;
    return 0;
}

考えた人間すごすぎる．

ハムスターでも分かった最長増加部分列

最長増加部分列とは？

Nが小さいとき

解法

コード