最长上升（下降、非升、非降）子序列的不同复杂度算法实现

描述

给定子序列，求最长的子序列，子序列满足上升（下降、非升、非降）的性质。

题目： http://www.luogu.org/problem/show?pid=1020
http://www.luogu.org/problem/show?pid=1091

分析&声明

以下讨论都以最长上升子序列为例。 序列为num 经典的dp问题，设序列长度为N，序列最大值为M（默认最小值为0）。 目前我所知道的有三种解法。

解法1：复杂度O(N ^ 2)

思路

创建一个数组best[]。best[i]表示序列中（0 ~ i）以num[i]结尾的最长长度。
则只需要寻找一个j(0 <= j < i)，使得：

1.num[j] < num[i]（若为下降，则为 > ，非升 >=， 非降 <=）。
2.best[j]最大。

这样，num[i]就能拼接在num[j]的后面，构成一个最长的子序列。 i遍历所有的num，求出best。遍历best，求出其中最大的即是结果。

状态转移方程

best[i] = max(best[j]) + 1, 其中(0 < j < i)

实现

int Longest_Increasing(vector<int> &num)
{
    vector<int> best(N, 0);
    for (int i = 0; i < N; i++){
        best[i] = 1;

        for (int j = 0; j < i; j++)
        if (num[i]>num[j] && best[j] + 1 > best[i])
            best[i] = best[j] + 1;
    }

    int maxn = 0;
    for (int i = 0; i < N; i++) 
    if (maxn<best[i]) 
        maxn = best[i];

    return maxn;
}

解法2：复杂度O(N * M)

此方法适用于M较小这种特殊的情况。

思路

同样通过dp方法解决，这一次创建的数组best对应的是序列中数字的大小，如best[20]，表示的是高度小于等于20的最长上升子串。 遍历一遍序列，更新best，从best[M]中得到结果。

状态转移方程

best[j] = max(best[num[i]] + 1, best[j])，其中（num[i] < j <= M）

实现

从0到N - 1遍历num。在遍历第i个数，即num[i]时，根据条件更新所有大于num[i]的高度对应的best值。即所有的j（（num[i] < j <= M）,对应的best[j]更新为max(best[num[i]] + 1, best[j]), 由于best是非减的，所以j只需要从num[i] + 1更新到best[j] >= best[num[i]] + 1即可以停止了。

int Longest_Increasing(vector<int> &num)
{
    vector<int> best(M + 1, 0);
    for (int i = 0; i < N; i++)
    {
        int h = num[i];
        for (int j = i + 1; j <= M && best[j] < best[h] + 1; j++)
            up[j] = up[h] + 1;
    }
    return best[M];
}

解法3：复杂度O(N * log(N))

此方法是对解法1的优化，比较复杂，但效率较高。具体可看：
http://blog.163.com/general_happy/blog/static/1693514082011024112934126/

思路

在解法1中，每次对应的num[i]，都要从0到i-1遍历best数组，找到相应的num[j]小于num[i]的最大best[j],这个遍历过程的复杂度是O(N)，此遍历可以用“二分查找”来优化。因为剔除掉所有num[j]大于等于num[i]的best项之后，剩下的best数组是递增的，即可以用二分法。复杂度下降到O(logN)。实现的时候当然不需要从新生成一个best数组，而是直接判断相应的项，若num[mid] >= num[i]，则直接忽略，令mid = mid - 1, 再次判断num[mid] >= num[i]即可。 这个链接进行了详细的说明，二分法时候有些许不同：
http://blog.csdn.net/wall_f/article/details/8295812