（SPOJ - ELIS ）Easy Longest Increasing Subsequence（DP）

Mike

　　Time limit1948 msMemory limit1572864 kBCode length Limit50000 B
　　Given 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[N],a[N];
int n;
int dfs(int sta)
{
  int& ret=dp[sta+1];
  if(ret!=-1) return ret;
  ret=0;
  for(int i=sta+1; i<n; i++)
  {
    if(sta==-1||a[i]>a[sta])
    {
      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[i]);
    //for(int i=0;i<n;i++)
    //  printf("%d\n",dp[i]);
    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[N],dp[N];
int n;
void solve()
{
  for(int i=0;i<n;i++)
    *lower_bound(dp,dp+n,a[i])=a[i];
  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[i]);
    solve();
  }
  return 0;
}