首页 > 专题系列 > 算法分析 > 动态规划(3)-最长递增子序列
2014
02-26

动态规划(3)-最长递增子序列

前面两讲:动态规划(1)-重叠子问题的性质 和 动态规划(2)-最优子结构的性质 我们已经讨论了重叠子问题和最优子结构性质。

现在我们讨论最长递增子序列(LIS)的问题,可以使用动态规划要解决的问题,例如,
最长递增子序列(LIS)的问题是要找到一个给定序列的最长子序列的长度,使得子序列中的所有元素被排序的顺序增加。

例如,{10,22,9,33,21,50,41,60,80}  LIS的长度是6和 LIS为{10,22,33,50,60,80}。

最优子结构:

对于长度为N的数组A[N] = {a0, a1, a2, …, an-1},假设假设我们想求以aj结尾的最大递增子序列长度,设为L[j],那么L[j] = max(L[i]) + 1, where i < j && a[i] < a[j], 也就是i的范围是0到j – 1。这样,想求aj结尾的最大递增子序列的长度,我们就需要遍历j之前的所有位置i(0到j-1),找出a[i] < a[j],计算这些i中,能产生最大L[i]的i,之后就可以求出L[j]。之后我对每一个A[N]中的元素都计算以他们各自结尾的最大递增子序列的长度,这些长度的最大值,就是我们要求的问题——数组A的最大递增子序列。

重叠子问题:

以下是简单的递归实现LIS问题(先不说性能和好坏,后面讨论)。这个实现我们遵循上面提到的递归结构。使用 max_ending_here 返回 每一个LIS结尾的元素,结果LIS是使用指针变量返回。

/* LIS 简单的递归实现 */
#include<stdio.h>
#include<stdlib.h>

/* 要利用递归调用,此函数必须返回两件事情:
   1) Length of LIS ending with element arr[n-1]. We use max_ending_here for this purpose
   2) Overall maximum as the LIS may end with an element before arr[n-1]  max_ref is used this purpose.
The value of LIS of full array of size n is stored in *max_ref which is our final result
*/
int _lis( int arr[], int n, int *max_ref)
{
    /* Base case */
    if(n == 1)
        return 1;

    int res, max_ending_here = 1; // 以arr[n-1]结尾的 LIS的长度

    /* Recursively get all LIS ending with arr[0], arr[1] ... ar[n-2]. If 
       arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs
       to be updated, then update it */
    for(int i = 1; i < n; i++)
    {
        res = _lis(arr, i, max_ref);
        if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)
            max_ending_here = res + 1;
    }

    // Compare max_ending_here with the overall max. And update the
    // overall max if needed
    if (*max_ref < max_ending_here)
       *max_ref = max_ending_here;

    // Return length of LIS ending with arr[n-1]
    return max_ending_here;
}

// The wrapper function for _lis()
int lis(int arr[], int n)
{
    // The max variable holds the result
    int max = 1;

    // The function _lis() stores its result in max
    _lis( arr, n, &max );

    // returns max
    return max;
}

/* 测试上面的函数 */
int main()
{
    int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Length of LIS is %d\n",  lis( arr, n ));
    getchar();
    return 0;
}

根据上面的实现方式,以下是递归树大小4的调用。LIS(N)为我们返回arr[]数组的LIS长度。

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

我们可以看到,有些重复的子问题被多次计算。所以我们可以使用memoization (记忆化存储)的或打表 来避免同一子问题的重新计算。以下是打表方式实现的LIS。

/* LIS 的动态规划方式实现*/
#include<stdio.h>
#include<stdlib.h>
/* lis() returns the length of the longest increasing subsequence in 
    arr[] of size n */
int lis( int arr[], int n )
{
   int *lis, i, j, max = 0;
   lis = (int*) malloc ( sizeof( int ) * n );

   /* Initialize LIS values for all indexes */
   for ( i = 0; i < n; i++ )
      lis[i] = 1;

   /* Compute optimized LIS values in bottom up manner */
   for ( i = 1; i < n; i++ )
      for ( j = 0; j < i; j++ )
         if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
            lis[i] = lis[j] + 1;

   /* Pick maximum of all LIS values */
   for ( i = 0; i < n; i++ )
      if ( max < lis[i] )
         max = lis[i];

   /* Free memory to avoid memory leak */
   free( lis );

   return max;
}

/* 测试程序 */
int main()
{
  int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
  int n = sizeof(arr)/sizeof(arr[0]);
  printf("Length of LIS is %d\n", lis( arr, n ) );

  getchar();
  return 0;
}

注意,上面动态的DP解决方案的时间复杂度为O(n ^ 2),其实较好的解决方案是 O(nlogn),这篇文章的目的是解释DP一个简单的例子,不做介绍了。

ACM之家原创:链接:

参考:http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  3. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.