（SPOJ - ELIS ）Easy Longest Increasing Subsequence（DP）
Time limit1948 msMemory limit1572864 kBCode length Limit50000 BGiven a list of numbers A output the length of the longest increasing subsequence. An increasing subsequence is defined as a set {i0 , i1 , i2 , i3 , … , ik} such that 0 <= i0 < i1 < i2 < i3 < … < ik < N and A[ i0 ] < A[ i1 ] < A[ i2 ] < … < A[ ik ]. A longest increasing subsequence is a subsequence with the maximum k (length).
i.e. in the list {33 , 11 , 22 , 44}
the subsequence {33 , 44} and {11} are increasing subsequences while {11 , 22 , 44} is the longest increasing subsequence.
Input
First line contain one number N (1 <= N <= 10) the length of the list A.
Second line contains N numbers (1 <= each number <= 20), the numbers in the list A separated by spaces.
Output
One line containing the lenght of the longest increasing subsequence in A.
Example
Input:
5
1 4 2 4 3
Output:
3
题意：求最长递增序列的长度
分析：可以利用记忆化取最大的来实现 如下解法1
解法1： 时间复杂度O(n^2)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=15;
#define mem(a,n) memset(a,n,sizeof(a))
int dp,a;
int n;
int dfs(int sta)
{
int& ret=dp;
if(ret!=-1) return ret;
ret=0;
for(int i=sta+1; i<n; i++)
{
if(sta==-1||a>a)
{
ret=max(ret,dfs(i)+1);
//printf("%d%d\n",i,ret);
}
}
return ret;
}
int main()
{
while(~scanf("%d",&n))
{
mem(dp,-1);
for(int i=0; i<n; i++)
scanf("%d",&a);
//for(int i=0;i<n;i++)
//printf("%d\n",dp);
printf("%d\n",dfs(-1));
}
return 0;
}
解法2： 内部实现过程见：https://www.felix021.com/blog/read.php?1587
时间复杂度O(nlogn)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mem(a,n) memset(a,n,sizeof(a))
const int INF=0x3f3f3f3f;
const int N=105;
int a,dp;
int n;
void solve()
{
for(int i=0;i<n;i++)
*lower_bound(dp,dp+n,a)=a;
printf("%d\n",lower_bound(dp,dp+n,INF)-dp);
}
int main()
{
while(~scanf("%d",&n))
{
mem(dp,INF);
for(int i=0;i<n;i++)
scanf("%d",&a);
solve();
}
return 0;
}
文档来源：51CTO技术博客https://blog.51cto.com/u_13696685/2989433
页:
[1]