思路

转了一个大神的博客

代码

sub中第i位表示，以a[i]结尾的最长上升子序列的长度。

这个代码只能解决正整数的LIS，而且还不优雅，我现在更新一种更好的板子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>  
#include <cstdio>
using namespace std;
#define inf 0x3f3f3f3f  
int const N = 1e5+5;
int a[N],sub[N],up[N];
int find(int *a,int len,int n)//若返回值为x,则a[x]>=n>a[x-1]  
{  
    int left=0,right=len,mid=(left+right)/2;  
    while(left<=right)  
    {  
        if(n>a[mid]) left=mid+1;  
        else if(n<a[mid]) right=mid-1;  
        else return mid;  
        mid=(left+right)/2;  
    }  
    return left;    
}  
       
void init(int *t,int n)  
{  
    for(int i=0;i<=n;i++)  
        t[i]=inf;  
    t[0]=-1;
    t[1]=a[0];
    sub[0]=1;
}  
       
int main(void)  
{  
    int max,i,j,n;  
    while(cin>>n)  
    {        
        memset(a,0,sizeof(a));
        memset(sub,0,sizeof(sub));
        memset(up,0,sizeof(up));
        for(i=0;i<n;i++)  
            cin>>a[i]; 
        init(up,n+1);  
        for(i=1;i<n;i++)
        {  
            j=find(up,n+1,a[i]);
            up[j]=a[i];
            sub[i]=j; 
        }  
        for(max=i=0;i<n;i++)
            if(sub[i]>max)  
                max=sub[i];  
       cout<<"max sub increase string 's lenth = "<<max<<endl;  
       cout<<"value for all position "<<endl;
       for(int i=0;i<n;i++){
        printf("%d%c",sub[i],i==n-1?'\n':' ');
       }
    }  
    return 0;  
}

改进版

离散化后可以解决所有整数问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>  
#include <cstdio>
#include <algorithm>
using namespace std;
#define inf 0x3f3f3f3f  
int const N = 1e5+5;
int a[N],b[N],sub[N],up[N];    
void init(int *t,int n)  
{  
    for(int i=0;i<=n;i++)  
        t[i]=inf;  
    t[0]=-1;
    t[1]=a[0];
    sub[0]=1;
}      
int main(void)  
{  
    int max,i,j,n;  
    while(cin>>n)  
    {   
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(sub,0,sizeof(sub));
        memset(up,0,sizeof(up));
        for(i=0;i<n;i++){
            cin>>a[i]; 
            b[i]=a[i];
        }
        sort(b,b+n);
        int size=unique(b,b+n)-b;
        for(i=0;i<n;i++)
            a[i]=lower_bound(b,b+size,a[i])-b+1;
        cout<<"离散化后的结果"<<endl;
         for(i=0;i<n;i++)
            printf("%d%c",a[i],i==n-1?'\n':' ');
        init(up,n+1);  
        for(i=1;i<n;i++)
        {  
            j=lower_bound(up,up+n+1,a[i])-up;
            up[j]=a[i];
            sub[i]=j;  
        }  
        
        for(max=i=0;i<n;i++)
            if(sub[i]>max)  
                max=sub[i];  
       cout<<"max sub increase string 's lenth = "<<max<<endl;  
       cout<<"value for all position "<<endl;
       for(int i=0;i<n;i++){
        printf("%d%c",sub[i],i==n-1?'\n':' ');
       }
    }  
    return 0;  
}

dp版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <complex>
#include <cstdio>
using namespace std;
#define ll long long
#define mod 110119
int dp[100];
int main(){
    int n,a[100];
    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);
        }
    }
    for(int i=1 ; i<=n ; i++)
        printf("%d%c",dp[i],i==n?'\n':' ');
    return 0;
}