最长上升子序列问题

问题描述
有一个长为n的子序列A0，A1···An-1。求出这个序列中最长的上升子序列的长度。上升子序列指的是对于任意的i<j都满足Ai<Aj的子序列。

我们定义dp[i]，表示以Ai为末尾的最长上升子序列的长度

以Ai结尾的上升子序列是：
只包含Ai的子序列
在满足j<i并且Aj<Ai的以Aj为结尾的上升子列末尾，追加上Ai后得到的子序列。

#include<iostream>
#include<stdio.h>
using namespace std;
int n;
int a[1000];
int dp[1000];
void solve()
{
    int ans=0;
    for(int i=0; i<n; i++)
    {
        dp[i]=1;
        for(int j=0; j<i; j++)
            if(a[j]<a[i])
            {
                dp[i]=max(dp[i],dp[j]+1);
            }
        ans=max(ans,dp[i]);
    }
    printf("%d
",ans);
}
int main()
{
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        scanf("%d",&a[i]);
    solve();
    return 0;
}

我们可以定义其他的递推关系
dp[i]，表示长度为i+1的上升子序列中末尾原始的最小值（不存在的话就是INF）。

#include<iostream>
#include<stdio.h>
#define INF 0x3f3f3f3f
using namespace std;
int n;
int a[1000];
int dp[1000];
void solve()
{
    for(int i=0;i<n;i++)
        dp[i]=INF;
        for(int i=0;i<n;i++)
            *lower_bound(dp,dp+n,a[i])=a[i];
            ///函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置
        printf("%d
",lower_bound(dp,dp+n,INF)-dp);
}
int main()
{
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        scanf("%d",&a[i]);
    solve();
    return 0;
}