最长递增子序列（LIS）求解

问题描写叙述

最长递增子序列也称 “最长上升子序列”，简称LIS ( longest increasing subsequence)。设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lis=<ak1,ak2,…,akm>。当中k1<k2<…<km且ak1<ak2<…<akm。求最大的m值。

如：求一个一维数组arr[i]中的最长递增子序列的长度，如在序列{ 7, 1, 6, 5, 3, 4, 8 }中，最长递增子序列长度为4，其递增子序列为：1。3，4，8。

问题解决

对于这类问题比較直观的想法是用动态规划，就像最长公共子序列(LCS)求解方法一样，对于动态规划问题。往往存在递推解决方法,须要首先建立递推关系。

方法1，DP求解

定义dp[i] : dp[i]为以arr[i]结尾的最长递增子序列的长度。对于第i个元素其递增序列长度最小值为1 即其自身。

对于以arr[i]结尾的递增序列。分两组情况：

A。仅仅包括arr[i]的子序列； B, 对于满足 j<i 且arr[i] > arr[j] 的以arr[j] 为结尾的递增子序列，然后追加上arr[i]得到的子序列；

相应的递推关系为：

dp[i] = max{1,dp[j]+1 | j<i 且 arr[j]<arr[i]}

使用这一递推公式就可以完毕LIS求解问题，代码例如以下：

#include <cstdio>
#include <algorithm>

const int MAX=16;

int dp[MAX];
//DP
//dp[i]表示以arr[i]为末尾的最长上升子序列的长度
int solve_lis_1(int *arr, int n)
{
    if(!arr || n<1)
        return -1;
    int res=0;
    for(int i=0; i<n; i++)
    {
        dp[i]=1;
        for(int j=0; j<i; j++)
        {
            if(arr[j]<arr[i])
                dp[i]=std::max(dp[i], dp[j]+1);
        }
         res=std::max(res, dp[i]);
    }
    return res;
}
int main()
{
    int a[]={7,1,5,3,4};
    printf("LIS:%d
", solve_lis_1(a, sizeof(a)/sizeof(int)));
    return 0;
}

其时间复杂度显然为 O(n^2).

方法2，DP+二分搜索

我们期望在前i个元素中的全部长度为len的递增子序列中找到这样一个序列，它的最大元素比arr[i+1]小。并且长度要尽量的长。如此，我们仅仅需记录len长度的递增子序列中最大元素的最小值就能使得将来的递增子序列尽量地长。

维护一个数组dp[i]，记录全部长度为i+1的递增子序列中末尾元素的最小值，并对于数组中的每一个元素考察其是那个子序列的末尾元素，二分更新dp数组，终于i的值便是最长递增子序列的长度。

总的说来就是。dp[i] 表示长度为i+1的上升子序列中末尾元素的最小值.

最開始全部dp[i]的值初始化为无穷大 INF，然后由前向后逐个考虑序列的元素，对于某个aj ,假设i=0或者dp[i-1] < aj, 就用dp[i]=min(dp[i], aj)进行更新。终于找出

dp[i]<INF的最大i+1就是答案了。

代码例如以下：

/*
 Problem:DP LIS,动态规划求解最长递增子序列
 Mem:挑战程序设计 P64
*/
#include <cstdio>
#include <algorithm>

const int MAX=16;

int dp[MAX];
//DP
//dp[i]表示以arr[i]为末尾的最长上升子序列的长度
int solve_lis_1(int *arr, int n)
{
    if(!arr || n<1)
        return -1;
    int res=0;
    for(int i=0; i<n; i++)
    {
        dp[i]=1;
        for(int j=0; j<i; j++)
        {
            if(arr[j]<arr[i])
                dp[i]=std::max(dp[i], dp[j]+1);
        }
         res=std::max(res, dp[i]);
    }
    return res;
}

// DP + 二分搜索
//dp[i] 表示长度为i+1的上升子序列中末尾元素的最小值
int solve_lis_2(int *arr, int n)
{
    const int INF=0xffffff;
    int i;
    for(i=0; i<n; i++)// 初始化dp[i]为 INF
        dp[i]= INF;
    for(i=0; i<n; i++)
    {
        *std::lower_bound(dp, dp+n, arr[i]) = arr[i];
    }
    return std::lower_bound(dp, dp+n, INF)-dp;
}

int main()
{
    int a[]={7,1,5,3,4};
    printf("LIS:%d
", solve_lis_1(a, sizeof(a)/sizeof(int)));
    printf("LIS:%d
", solve_lis_2(a, sizeof(a)/sizeof(int)));
    return 0;
}

当中二分查找算法是利用STL的lower_bound 函数这个函数在有序序列中利用二分搜索技术找到指向满足 ai>=k的ai最小指针,參见这里。

对于序列{7,1,5,3,4} 方法 solve_lis_2 dp数组变化如图所看到的。

方法2的时间度为：由于二分查找的复杂度为O(logn) 加上外层循环，整体复杂度为 O(nlogn)。

參考:

http://www.ahathinking.com/archives/117.html