LIS + Problem

前1个数 d[1]=1 子序列为2；

　　前2个数 7前面有2小于7 d[2]=d[1]+1=2 子序列为2 7

　　前3个数 在1前面没有比1更小的，1自身组成长度为1的子序列 d[3]=1 子序列为1

　　前4个数 5前面有2小于5 d[4]=d[1]+1=2 子序列为2 5

　　前5个数 6前面有2 5小于6 d[5]=d[4]+1=3 子序列为2 5 6

　　前6个数 4前面有2小于4 d[6]=d[1]+1=2 子序列为2 4

　　前7个数 3前面有2小于3 d[3]=d[1]+1=2 子序列为2 3

　　前8个数 8前面有2 5 6小于8 d[8]=d[5]+1=4 子序列为2 5 6 8

　　前9个数 9前面有2 5 6 8小于9 d[9]=d[8]+1=5 子序列为2 5 6 8 9

　　d[i]=max{d[1],d[2],……,d[i]} 我们可以看出这9个数的LIS为d(9)=5

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1010;

int a[N],dp[N];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i],dp[i] = 1;
    dp[0] = 1;
    for(int i=1;i<=n;++i)
    {
        for(int j =1;j<i;++j)
        {
            if(a[j]<a[i])
            {
                //当前状态与把a[j]加入序列的状态的长度比较，取最大值。
                dp[i] = max(dp[i],dp[j]+1);
                
            }
        }
    }
    int ans = -0x3f3f3f3f ;
    for(int i =1;i<=n;++i)
        ans = max(ans,dp[i]);
    cout<<ans<<endl;
    system("pause");

    return 0;
}

//时间复杂度O(n^),可以优化到o(nlogn)

我们再举一个例子：有以下序列A[ ] = 3 1 2 6 4 5 10 7，求LIS长度。

　　我们定义一个B[ i ]来储存可能的排序序列，len 为LIS长度。我们依次把A[ i ]有序地放进B[ i ]里。

     （为了方便，i的范围就从1~n表示第i个数）

　　A[1] = 3，把3放进B[1]，此时B[1] = 3，此时len = 1，最小末尾是3

　　A[2] = 1，因为1比3小，所以可以把B[1]中的3替换为1，此时B[1] = 1，此时len = 1，最小末尾是1

　　A[3] = 2，2大于1，就把2放进B[2] = 2，此时B[ ]={1,2}，len = 2

　　同理，A[4]=6，把6放进B[3] = 6，B[ ]={1,2,6}，len = 3

　　A[5]=4，4在2和6之间，比6小，可以把B[3]替换为4，B[ ] = {1,2,4}，len = 3

　　A[6] = 5，B[4] = 5，B[ ] = {1,2,4,5}，len = 4 

　　A[7] = 10，B[5] = 10，B[ ] = {1,2,4,5,10}，len = 5

　　A[8] = 7，7在5和10之间，比10小，可以把B[5]替换为7，B[ ] = {1,2,4,5,7}，len = 5

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1010;

int a[N],low[N];
int bin_search(int R,int x)
{
    int l = 1,r=R;
    while(l<=r)
    {
        int mid = (l+r)>>1;
        if(low[mid]<x)
            l = mid+1;
        else
        {
            r = mid-1; 
        }
        
    }
   return l;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i],low[i] = INF;
    
    low[1] = a[1];
    int ans = 1;
    for(int i=2;i<=n;++i)
    {
        if(a[i]>low[ans])
            low[++ans] = a[i];
        else
        {
            low[bin_search(ans,a[i])] = a[i];
        }
    }
    cout<<ans<<endl;
    system("pause");

    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N],dp[N];

int main()
{
    while(cin>>n&&n!=0)
    {
        memset(dp,0,sizeof(0));
        for(int i =1;i<=n;++i)
            cin>>a[i],dp[i] = a[i];
        
        

        for(int i =2;i<=n;++i)//从第2开始
        {
            for(int j =1;j<i;++j)
            {
                if(a[j]<a[i])
                    dp[i] = max(dp[i],dp[j]+a[i]);
            }
        }
        int ans = dp[1];
        for(int i =1;i<=n;++i)
        {
            ans = max(ans,dp[i]);
        }
        cout<<ans<<endl;
    }
    system("pause");
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 3030;
int a[N];
int dp[N];
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=1;i<=n;++i)
        {
            cin>>a[i];
            dp[i] = 1;
        }
        for(int i =1;i<=n;++i)
        {
            for(int j=1;j<i;++j)
            {
                if(a[j]<a[i])
                    dp[i] = max(dp[i],dp[j]+1);
            }
        }
        int ans = -1;
        for(int i =1;i<=n;++i)
            ans = max(ans,dp[i]);
        cout<<ans<<endl;
        
    }
    system("pause");
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std ;

const int N = 40010;

int a[N],dp[N],low[N];
int n;
int bin_search(int R,int x)
{
    int l =1,r = R;
    while(l<=r)
    {
        int mid = (l+r)>>1;
        if(low[mid]<x) l = mid+1;
        else
        {
            r = mid-1;
        }
        
    }
    return l;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i =1;i<=n;++i)
        {
            cin>>a[i];
            //low[i] = 0x3f3f3f3f;
            
        }
        int ans = 1;
        low[1] = a[1];
        for(int i =2;i<=n;++i)
        {
            if(a[i]>low[ans])
                low[++ans] = a[i];
            else
            {
                low[bin_search(ans,a[i])] = a[i];
            }
            
        }
        cout<<ans<<endl;
    }
    system("pause");
    return 0;
}