長さnの数列a0,a1,…,an-1がある。 この数列の増加部分列うち、最長のものの長さを求めよ。 ただし、増加部分列とは、全てのi<jでai<ajを満たす部分列のことを言う。

漸化式を立ててみると、
dp[i] := 長さがi+1である増加部分列における最終要素の最小値(存在しない場合INF)
となる。以下、C++のコード。

#include <iostream>
#include <vector>
using namespace std;

#define INF 1e+9
#define MAX_N 1000

int dp[MAX_N];
int n;
vector<int> a;

void solve() {
    fill(dp, dp+n, INF);
    for (int i=0; i<n; ++i) {
        *lower_bound(dp, dp+n, a[i]) = a[i];
    }
    cout << lower_bound(dp, dp+n, INF) - dp << endl;
}

int main() {
    cin >> n;
    a.resize(n);
    for(int i=0; i<n; ++i) cin >> a[i];
    solve();
}

計算量はO(n log n).