紫书第九章-----动态规划初步（最长递增子序列LIS）

最长递增子序列

给出一个数字序列求其最长的递增子序列例如序列(1,7,3,5,9,4,8)。(1,7)和(3,4,8)是其递增子序列但其最长的递增子序列是(1,3,5,8)。有了前面的动态规划的基础，下面直接用例题来解决此问题。

【例题：最长递增子序列 HRBUST - 1835 】

- 规划方向1

/*
    状态：d(i)表示以a[i]开头（笔者采用此规划方向，当然可以与笔者规划方向相反）的最长严格递增子序列的长度
    状态转移：d(j)=max(d(j),d(i)+1),j<i && a[j]<a[i]
*/

#include<iostream>

using namespace std;

const int maxn=50000+5;
int dp[maxn];
int a[maxn];
int n;

int main()
{
    while(cin>>n){
        for(int i=1;i<=n;i++){
            cin>>a[i];
            dp[i]=1;
        }
        //注意i枚举的顺序是从n到1进行枚举的
        for(int i=n;i>=1;i--){
            for(int j=1;j<i;j++){
                if(a[j]<a[i]){
                    dp[j]=max(dp[j],dp[i]+1);
                }
            }
        }
        int max_len=dp[1];
        for(int i=1;i<=n;i++) max_len=max(dp[i],max_len);
        cout<<max_len<<endl;
    }
    return 0;
}

- 规划方向2

/*
    状态：d(i)表示以a[i]结束的最长严格递增子序列的长度
    状态转移：d(j)=max(d(j),d(i)+1),j>i && a[j]>a[i]
*/

#include<iostream>

using namespace std;

const int maxn=100+5;
int dp[maxn];
int a[maxn];
int n;

int main()
{
    while(cin>>n){
        for(int i=1;i<=n;i++){
            cin>>a[i];
            dp[i]=1;
        }
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(a[j]>a[i]){
                    dp[j]=max(dp[j],dp[i]+1);
                }
            }
        }
        int max_len=dp[1];
        for(int i=1;i<=n;i++) max_len=max(dp[i],max_len);
        cout<<max_len<<endl;
    }
    return 0;
}

上面代码的时间复杂度显然是O(n^2)，可以解决这个题目，但是下面的这道题目采用同样的代码就解决不了了，主要是时间复杂度的问题！下面就利用下面的这道例题对上述代码进行时间复杂度的优化，优化到O(nlogn)。具体如下。

【例题：最长递增子序列 51Nod - 1134 】

笔者以上面的规划方向2为启发思维的背景，进行优化代码（规划方向1逆向而行，行不通）。规划方向2是正向规划，即按照给出的序列的从左向右的方向进行规划。用len表示当前最大长度，goal[len]表示当前要放到最终上升序列中的数。枚举数组a的过程中，不断更新goal数组，当出现a[i]<=goal[len]的时候，要用a[i]去替换掉goal数组中相应的元素来保证goal始终是严格递增的序列，这样最终的goal数组其实就是字典序最小的严格上升的子序列，len就是这个序列的长度。

/*
    状态：d(i)表示以a[i]结束的最长严格递增子序列的长度
    状态转移：d(j)=max(d(j),d(i)+1),j>i && a[j]>a[i]
*/

#include<iostream>

using namespace std;

const int maxn=50000+5;
int goal[maxn];
int a[maxn];
int n;

//注意下面的二分查找相当于lower_bound函数，在[l,r)内查找大于等于v的最小下标，
//如果不存在，会一直往右跑(l=mid+1)，返回的是r
int bin_search(int a[],int l,int r,int v){
    int mid;
    while(l<r){
        mid=l+(r-l)/2;
        if(v<=a[mid]) r=mid;
        else l=mid+1;
    }
    return l;
}

int main()
{
    while(cin>>n){
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        int len=1;
        goal[1]=a[1];
        for(int i=2;i<=n;i++){
            if(a[i]>goal[len]){ //如果a[i]>goal[len]，goal往后走
                goal[++len]=a[i];
            }else{  //如果a[i]<=goal[len]，goal不能继续延长，这时候，在goal[1]~goal[len]中进行查找
                    //找到大于等于a[i]的最小值对应的下标k，由于goal本身就是从小到大的顺序，则不仅可
                    //用二分法查找，而且以a[i]结束的最长递增序列长度是k，并且最巧妙的是可以用a[i]代替
                    //goal[k]，这样不仅保证了尽量小的值放在前面（关键），而且保证了求得的是最小字典序
                    //打印goal数组，就是最小字典序的序列
                int pos=bin_search(goal,1,len+1,a[i]);//二分查找
                                //上面一句代码等价于这个：int pos=lower_bound(goal+1,goal+len+1,a[i])-goal;
                goal[pos]=a[i];
            }
        }
        cout<<len<<endl;
    }
    return 0;
}