最长递增子序列

#include <iostream>
using namespace std;
//int num[8]={0,0,3,1,2,4,1,5};//原始序列
int num[8]={0,1,3,4,2,5,6,7};
int d[8];//保存最长递增子序列的元素,第二种方法，复杂度低
int dp[8];//第一种方法,复杂度高，dp[i]存储从num[1]到num[i]之间最长递增子序列的长度，num[i]一定在里边
int BinSearch(int key,int i,int low,int high)//二分搜索,找到road[i]在d[]数组中的位置
{
    int l=low,r=high;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(num[i]<=d[mid])
            r=mid-1;
        else
            l=mid+1;
    }
    return l;
}
int LIS()
{
    d[1]=num[1];
    int len=1;//最长递增子序列的元素个数
    int j;
    for(int i=2;i<=7;i++)
    {
        if(d[len]<num[i])
            j=++len;
        else
            j=BinSearch(num[i],i,1,len);
        d[j]=num[i];
    }
    return len;//d[]数组中保存的原始序列中的最长递增子序列的元素个数
}

/*int LIS(int num[],int n)
{
    int ans=1;
    int m;
    dp[1]=1;
    for(int i=2;i<=n;i++)
    {
        m=0;
        for(int j=1;j<i;j++)
        {
            if(dp[j]>m&&num[j]<num[i])
                m=dp[j];
        }
        dp[i]=m+1;
        if(dp[i]>ans)
            ans=dp[i];
    }
    return ans;
}*/
int main()
{
    //第二种方法，复杂度低，二分搜索，可以保存最长递增子序列的元素
    int len=LIS();
    cout<<len<<endl;
    for(int i=1;i<=len;i++)
       cout<<d[i]<<endl;//输出原始序列中构成最长递增子序列的元素。*/

    //第一种方法，复杂度高，只能返回最长递增子序列的长度
    /*int len=LIS(num,7);
    cout<<len<<endl;
    for(int i=1;i<=7;i++)
        cout<<dp[i]<<endl;*/
    return 0;
}