最长上升子序列问题

 最长上升子序列问题

有一个长为n的数列请求出这个序列中最长的上升子序列的长度，上升子序列值的是对于任意的,都满足的子序列。

N的范围决定与算法的选择

1<=N<=10000

这个问题也被称为最长递增子序列（LIS）

首先建立递推关系：

定义

dp[i]:=以为末尾的最长递增子序列的长度

以结尾的上升子序列是：

只包含的子序列

在满足并且的以为结尾的上升序列末尾，追加后得到的子序列

这二者之一，就能得到如下的递推公式：

代码：

//输入

int n;
int a[N];
int dp[N];

void solve()
{
    int res=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);
        }
        res=max(res,dp[i]);
    }
    printf("%d\n",res);
}</span>

此外还可以定义其他递推关系，前面我们利用DP求取针对最末位的元素的最长递增子序列，如果子序列的长度相同

那么最末位的元素较小的在之后会更有优势，所以可以考虑反过来用DP针对相同长度情况下最小的末位元素进行求解

dp[i]:=长度为的上升序列中末位元素的最小值（不存在的话为INF）

  用DP来更新这个数组：

最开始全部DP数组赋值INF ,然后由前到后逐个考虑数列的元素，对于每个,如果i==0,或者

的话，就用dp[i]=min(dp[i],)进行更新，最终找出使得dp[i]<INF的最大的i+1

就是结果，此方法为考虑进一步优化，首先dp数组中除INF之外是单调递增的，所以对于每个最多需要更新1次，对于更新位置可以进行二分搜索进行加速，复杂度O(nlogn)。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int b[N],c[N];
int num[N];
int ans[N];
int LIS1(const int *a,int n)
{
    b[1]=a[0];
    int len=1;
    for(int i=1; i<n; ++i)
    {
        int k=lower_bound(b+1,b+len+1,a[i])-b;
        if(k>len) len++;
        b[k]=a[i];
    }
    return len;
}
int LIS2(const int *a,int n)
{
    int len=1,Left,Right,mid;
    c[1]=a[0];    ///初始时，最大递增子序列长度为1的最末元素为a1
    for(int i=1; i<n; i++)
    {
        Left=1;   ///左边初始长度为1
        Right=len;///右边表示当前所求长度
        while(Left<=Right)///二分查找最末元素小于ai+1的长度最大的最大递增子序列；
        {
            mid=(Left+Right)/2;
            if(c[mid]<a[i]) Left=mid+1;
            else Right=mid-1;
        }
        c[Left]=a[i];///将长度为Left的最大递增子序列的当前最末元素置为ai+1;
        if(Left>len) len++;///更新当前最大递增子序列长度；
    }
    return len;
}

最长上升子序列问题

原文：http://blog.csdn.net/u013050857/article/details/48806097