最长上升子序列

80 阅读 0 评论 53 点赞

我是靠谱客的博主想人陪钥匙，最近开发中收集的这篇文章主要介绍最长上升子序列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在这试验一下

题目描述
给出一个由n个数组成的序列A[1…n]，求最长单调上升子序列（LIS)的长度。LIS即求最大的一个子序列长度m，使得a1<a2<……<am且A[a1]<A[a2]<……<A[am]。

输入
两行：
第1行：整数n (1<=n<=1000)
第2行：n个整数（int范围内），空格隔开。

输出
一行：一个整数，即最长上升子序列长度。

样例输入

10
63	11	21	36	28	20	57	37	82	4
5
4 2 3 1 5

样例输出

5
3

解析一：

时间复杂度是O（n^2）
code：

#include <iostream>
#define inf 0x7fffffff
#include <algorithm>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
int a[1100];
int dp[1100];
int i,j,re=0;
for(i=0; i<n; i++)
cin>>a[i];
for(i=0; i<n; i++)
{
dp[i]=1;
for(j=0; j<i; j++)
{
if(a[i]>a[j])
dp[i]=max(dp[i],dp[j]+1);
}
re=max(re,dp[i]);
}
cout<<re<<endl;
}
return 0;
}

解析二：

知识补充：
lower_bound() 函数返回一个迭代器，指向map中键值>=key的第一个元素。
lower_bound：这个函数从已经排好序的的序列 a 中利用二分搜索找出指向 ai>=k 的 ai 的最小指针。
upper_bound：求出的是满足 ai>k 的 ai 的最小指针。

例子：求长度为n 的有序数组a 中 k 的个数。
upper_bound(a,a+n,k) - lower_bound(a,a+n,k)

fill() 可以返回当前填充字符，或者设置当前填充字符为ch 。填充字符被定义为用来填充字符，当一个数
字比较指定宽度T小时。默认的填充字符是空格。
memset 和 fill 区别：
memset 只能初始化0 -1
fill 可以初始化所有

过程：
4 ~ ~ ~ ~
2 ~ ~ ~ ~
2 3 ~ ~ ~
1 3 ~ ~ ~
1 3 5 ~ ~

#include <iostream>
#define inf 0x7fffffff
using namespace std;
/*
int main()
{
int n;
while(cin>>n)
{
int a[1100];
int dp[1100];
int i,j;
for(i=0; i<n; i++)
{
cin>>a[i];
dp[i]=inf;
}
for(j=0; j<n; j++)
{
for(i=0; i<=j; i++)
{
if(i==0||dp[i-1]<a[j])
dp[i]=min(dp[i],a[j]);
}
}
for(i=0; i<n; i++)
{
if(dp[i]==inf)
{
cout<<i<<endl;
break;
}
}
}
return 0;
}
*/
int main()
{
int n;
while(cin>>n)
{
int a[1100];
int dp[1100];
int i;
fill(dp,dp+n,inf);
for(i=0; i<n; i++)
cin>>a[i];
for(i=0;i<n;i++)
{
*lower_bound(dp,dp+n,a[i])=a[i];
}
cout<<lower_bound(dp,dp+n,inf)-dp<<endl;
}
return 0;
}