最长上升子序列

如果一个数列ai 满足 a1 < a2 < … < aN 则这个数列被称作上升序列。

给定一个数列a(a1, a2, …, aN)则任意一个数列b(ai1, ai2, …, aiK)并且满足（1 <= i1 < i2 < … < iK <= N）.则b被称为a的子序列。

如果一个数列的子序列是上升序列，则这个序列称为原序列的上升子序列。

比如序列(1, 7, 3, 5, 9, 4, 8)的上升子序列有(1, 7), (3, 4, 8)等. 它的最长上升子序列长度是4,即(1, 3, 5, 8).

请你写一个程序求一个序列的最长上升子序列的长度。

Input
第一行是一个整数N表示给定数列的长度. 第二行包括N个范围在0～10000的整数。 1 <= N <= 1000

Output
输出一个整数表示最长上升子序列的最大长度

SampleInput
7
1 7 3 5 9 4 8
SampleOutput
4

最长上升子序列（LIS）两种方法
1.暴力法
开两层循环然后记长度复杂度O（n²），这里不过多介绍主要说下一种
2.二分
最长上升子序列。可以知道选的数是上升的可以不连续比如3 5 6也是子序列。。
我们可以把这个子序列模拟成一个栈。。是的，如果这个数比栈顶的数大，那么就入栈。那么如果比栈顶小呢？要舍去吗？不然。这里给个如下的例子：
4 6 5 6 7
显然最长上升子序列长度为4
4 6进栈了然后5小于栈顶6 就在这个栈中找到第一个大于等于5的数A 用5取代这个数A.
（想一下为什么）
这个栈数单调递增的所以可以采用二分。
这里解释下上面取代的原因吧 5取代6的原因是如果5后面还有6的话这样就是4 5 6的栈而不是4 6 7了就算后面没有6 也不影响前面取代的长度值因为要的是长度最大。
如果把小的数A舍去如果后面还有栈顶的数的话可能会忽略到A到栈顶之间的数

。

复杂度为o（n*logn）一层循环n 一个二分logn。。话不多说上代码。

#include<iostream>
#include<algorithm>
using namespace std;
int a[1001],b[1001];
int main()
{
    int n,i;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    b[1]=a[1];
    int len=1;
    for(i=1;i<=n;i++)    /// 4 6 5 6 /// 4 6 4 5 6
    {
        if(a[i]>b[len])
            b[++len]=a[i];
        else
        {
            int j=lower_bound(b+1,b+len+1,a[i])-b;
            /// 这是c++的下界函数，也可手写二分实现
            b[j]=a[i];

        }
    }
    cout<<len;
}

如果有更好的方法还请留言下。。