最长上升子序列

最长上升子序列(Longest Increasing Subsequence),简称 LIS,即在一个给定的数值序列中,找到一个子序列,使得这个子序列元素的数值依次递增,并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的,比如

{0, 8, 4, 12, 2, 10}
最长上升子序列为
0, 4, 10 - 长度为 3

{34,2,4,33,32,35}
最长上升子序列为
2,4,32,35 - 长度为 4

{4}
最长上升子序列为
4 - 长度为 1

算法实现

假设长度为 n 的数组 arr,这里的 i 代表 arr[i] 即为子序列结尾元素
L(i) = 1 + max(L(j)) 需要满足 0 < j < i 且 arr[j] < arr[i]
L(i) = 1 如果 j 不存在

比如

求 arr[] = {50,33,34,40,1} 的最长上升子序列长度
即求解 MAX( L(1),L(2),L(3),L(4),L(5) )
L(1) = 1
L(2) = 1 (因为50 > 33 即 j 不存在)
L(3) = 1 + MAX( L(2) ) = 2 因为 50 > 34

L(4) = 1 + MAX( L(3), L(2) ) 因为 50 > 40
由上可值 L(3) = 2, L(2) = 1 即 MAX( L(3), L(2) ) == 2
即L(4) = 1+2 = 3

L(5) = 1

可得 MAX( L(1),L(2),L(3),L(4),L(5) ) = L(4) = 3
即arr最长上升子序列长度为3


例子-1

#include <stdio.h>

int lis(int *arr, int n) 
{ 
    int i,res,max = 1;

    if (n == 1) return 1;

    for (i = 1; i < n; i++) {
        // 过滤掉不比自己小的
        if (arr[i - 1] >= arr[n - 1])
            continue;
        res = lis(arr, i);
        // found
        if (res + 1 > max)
            max = res + 1;
    }

    return max;
} 

int main()
{
    int arr[] = {34,2,4,33,32,35};
    int n = sizeof(arr) / sizeof(int);
    printf("length of lis is %d\n", lis(arr, n));
    return 0;
}

上面解法包含重叠子问题,下面是一个求长度为4的数组的LIS长度,可以看出出现了很多重复

              lis(4)
        /        |      \
      lis(3)    lis(2)   lis(1)
     /     \      |
   lis(2) lis(1) lis(1)
   /
lis(1)


例子-2

下面是利用表格法(tabular method)实现

#include <stdio.h>

#define dl_max(x,y) ((x) > (y) ? (x) : (y))
int lis(int *arr, int n) 
{ 
    int     i,j,max;
    int     ls[n];

    max = 1;
    ls[0] = 1;

    printf("L(%d) = %d\n", 1,1);
    for (i = 1; i < n; i++) {
        ls[i] = 1;

        for (j = 0; j < i; j++) {
            if (arr[j] < arr[i] && ls[j] + 1 > ls[i])
                ls[i] = ls[j] + 1;
        }
        
        if (ls[i] > max)
            max = ls[i];

        printf("L(%d) = %d\n", i+1,ls[i]);
    }

    return max;
} 

int main()
{
    int arr[] = {34,2,4,33,32,35,1};
    int n = sizeof(arr) / sizeof(int);
    printf("length of lis is %d\n", lis(arr, n));
    return 0;
}
[root@dldl ccc]# ./a.out 
L(1) = 1
L(2) = 1
L(3) = 2
L(4) = 3
L(5) = 3
L(6) = 4
L(7) = 1
length of lis is 4


上一篇: 编辑距离
下一篇: 最长公共子序列
作者邮箱: 203328517@qq.com