最长上升子序列（LIS）——动态规划

问题描述

  给定n个数字的序列，如11，3，6，9，13，14，18，12，15，2，16，20，8，19，问最长的上升序列长度是多少。
  上升序列，分为严格单调递增序列和单调不减序列。前者需满足序列L中，i<j，L[i]<L[j]，而后者可取等号。例如，上述序列中存在一个递增序列{3，8，19}，显然不是最长的上升子序列。

分析

  因为递增的判断是在原序列末尾元素基础上进行比较的，是动态规划典例。递推关系如下：
  对于每个元素s[i]，向前找所有小于s[i]的元素。

• 若存在s[j]<s[i]（j<i），则dp[i] = max{dp[j]} + 1
• 若不存在s[j]<s[i]（j<i）,则s[i]自身构成一个子序列，dp[i] = max{dp[k]}，k为小于i的整数
  可以得出
  dp[1]=1, dp[2]=1, dp[3]=2, dp[4]=3, dp[5]=4, dp[6]=5, dp[7]=6, dp[8]=6, dp[9]=6, dp[10]=6, dp[11]=7, dp[12]=8, dp[13]=8, dp[14]=8

代码实现

#include <iostream>
#include <cstring>

using namespace std;
const int maxn = 205;
int s[maxn], dp[maxn];

int main()
{
    int n; cin >> n;
    for(int i=0;i<n;i++) cin >> s[i];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    int i;
    for(i=1;i<n;i++){
        int tem_max=0;
        for(int j=0;j<i;j++){
            if(s[j]<s[i]) tem_max = max(tem_max, dp[j]);
        }
        dp[i] = tem_max+1;
    }
    cout << dp[n-1];
    return 0;
}

  上面代码的复杂度为O(n^n)，每次考虑一个元素都需要和它之前的数依次比较一遍，比较笨。我们思考是否可以用一个数组保存当前最佳的最长子序列，这样每次新加入一个数，只需将其与数组最后一个元素比较即可。
  这会引入一个问题，保存的最长上升子序列的数组是动态变化的，并且为贪心使尽可能更多的元素加入，需要不断修改数组元素为不改变大小关系的最小值。
  例如，已有当前的最长子序列{3，6，9，13，14，18}，当遇到12时，比较18>12，那么寻找数组中第一个大于12的元素将其替换。处理完12得到的子序列是{3，6，9，12，14，18}，长度不变，需要特别注意的是，此序列不能代表真实的最长上升子序列，只是为求解序列长度提供的一种量化方法。
  将复杂度降到O(nlgn)，代码如下

#include <iostream>
#include <cstring>

using namespace std;
const int maxn = 205;
int s[maxn], lis[maxn];

int bi_search(int A[], int right, int left, int num){ //二分查找递增数列a[n]中第一个大于num的元素下标，并返回
    int mid;
    while(right<left){
        mid = (right+left)/2;
        if(num<=A[mid]) left = mid;
        else right = mid+1;
    }
    return left;
}
int main()
{
    int n; cin >> n;
    int maxl;
    for(int i=0;i<n;i++) cin >> s[i];
    memset(lis, 0, sizeof(lis));
    lis[0] = s[0]; maxl = 1; //maxl表示lis数组元素个数，即最长上升子序列长度
    for(int i=1;i<n;i++){
        if(lis[maxl-1]<s[i])
            lis[maxl++] = s[i];
        else if(lis[maxl-1]==s[i]) continue;
        else{
            int p = bi_search(lis, 0, maxl-1, s[i]);
            lis[p] = s[i];
        }
    }
    cout << maxl;
    return 0;
}

注意

  上面两个算法都不能直接求出最长上升子序列