首页 > 其他 > 详细

最长上升子序列

时间:2015-03-12 20:47:28      阅读:225      评论:0      收藏:0      [点我收藏+]
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int Maxn=1010;
int dp[Maxn];
int main()
{
    int t;
    int n,num[Maxn];
    while(~scanf("%d",&n)){
        for(int i=0;i<n;i++){
            scanf("%d",&num[i]);
        }
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++){
            dp[i]=1;
            for(int j=0;j<n;j++){
                if(num[i]>num[j] && dp[i]<dp[j]+1){
                    dp[i]=dp[j]+1;
                }
            }
        }
        int ans=0;
        for(int j=0;j<n;j++){
            ans=max(ans,dp[j]);
        }
        cout<<ans<<endl;
    }
    return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int Maxn= 1010;
int main()
{
    int n,num[Maxn],temp[Maxn];
    while(~scanf("%d",&n)){
        for(int i=0;i<n;i++){
            scanf("%d",&num[i]);
        }
        int cnt=1;
        temp[0]=num[0];
        for(int i=0;i<n;i++){
            if(num[i]>temp[cnt-1]){
                temp[cnt++]=num[i];
            }
            else{
                int s=lower_bound(temp,temp+cnt,num[i])-temp;
                temp[s]=num[i];
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

 

最长上升子序列

原文:http://www.cnblogs.com/Scale-the-heights/p/4333346.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!