给定 n 个整数 A_1,A_2,\\cdots,A_n，按从左到右选出尽量多的整数，组成一个上升的子序列．比如，从序列1, 6, 2, 3, 7, 5 中，可以选出上升子序列 1, 2, 3, 5，也可以选出 1, 6, 7，但前者更长．注意，所选出的上升子序列中相邻元素不相等．

有两种办法．

第一种具有 O(n^2) 的复杂度．dp[i]表示以第ｉ个数的最大上升子序列的个数，那么就有 dp[i]=\\max(0, d(j)|A_i\\lt A_j, i \\lt j) + 1

第二种具有 O(n \\log{n})的复杂度．

假设已经计算出的两个状态 a 和 b 满足 A_a \\lt A_b且 d(a)=d(b)，则对于后续所有状态 i （即 i>a 且 i>b），ａ并不会比ｂ差——如果 b 满足 A_b \\lt A_i的条件时，ａ也满足，且二者的ｄ值相同；但反过来却不一定了，ａ满足 A_a \\lt A_i的条件时，ｂ却不一定满足．换句话说，如果我们只保留ａ，一定不会丢失最优解．

这样，对于相同的ｄ值，只需保留Ａ最小的一个．用 g(i)表示ｄ值为ｉ的最小状态编号（如果不存在，g(i)定义为正无穷）．根据上述推理可以证明

g(1)\\leq g(2) \\leq \\cdots \\leq g(n)

ｇ是动态改变的．给定状态ｉ，我们只考虑在ｉ之前已经计算过的状态ｊ（即ｊ＜ｉ），上述ｇ序列也是基于这些状态的．随着ｉ的不断增大，要考虑的状态也越来越多，ｇ也随之发生改变．在给定状态ｉ时，可以用二分查找得到满足 g(k) \\geq A_i的第一个下标ｋ，则 d(i)=k，此时 A_i \\lt g(k)，所以更新g(k)=A_i．

举个例子：求 A[5] = [1, 6, 2, 3, 7, 5] 的最长上升子序列．

1. 将A[0]放入G[]，得 G[0] = {1}
2. 将A[1]放入G[]，得 G[0, 1] = {1, 6}，这里由于A[1]比第一步的 G[] 中最大的一个元素还要大，所以加到 G[] 的末尾．
3. 将A[2]放入G[]，得 G[0, 1] = {1, 2}，这里由于２小于６，所以把６改为２
4. 将A[3]放入G[]，得 G[0, 1, 2] = {1, 2, 3}，这里由于A[3]比第３步的 G[] 中最大的一个元素还要大，所以加到G[]的末尾．
5. 将A[4]放入G[]，得 G[0, 1, 2, 3] = {1, 2, 3, 7}
6. 将A[5]放入G[]，得 G[0, 1, 2, 3] = {1, 2, 3, 5}

所以，最后最长公共子序列的个数也就是 G[] 中元素的个数．通常用二分查找来查找 A[i] 在 G[] 中的位置，因此算法时间复杂度 O(n\\log{n})

for (int i = 1; i <= n; i++)
    g[i] = INF;
for (int i = 0; i < n; i++) {
    int k = lower_bound(G + 1, G + n + 1,  A[i]) - G;
    d[i] = k;
    G[k] = A[i];
}

题目链接：http://poj.org/problem?id=2533

第一种方法的代码：

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1005;
int a[N], dp[N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", a + i);
    int ans = 1;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[i] > a[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    printf("%d\n", ans);
    return 0;
}

第二种方法的代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1005;
int a[N], g[N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", a + i);
    int ans = 0;
    memset(g, INF, sizeof(g));
    for (int i = 0; i < n; i++) {
        int k = lower_bound(g, g + n, a[i]) - g;
        g[k] = a[i];
        ans = max(ans, k + 1);
    }
    printf("%d\n", ans);
    return 0;
}