[动态规划-1] 最长递增子序列-Longest Increasing Subsequence - c++编程基础

问题描述：求一个一维数组arr[i]中的最长递增子序列的长度，如在序列1，-1，2，-3，4，-5，6，-7中，最长递增子序列长度为4，可以是1，2，4，6，也可以是-1，2，4，6。

问题分析：

我们用L(i)表示从arr[0]---arr[i]的以arr[i]结尾的最长递增子序列的长度值，那么：

L(i) = 1 + Max(L(j)),当满足j < i,且arr[j] < arr[i]时；

L(i) = 1,当不满足上面条件时，也就是说arr[i]前面没有比它更小的数字。

代码：

#include  
#include  
   
/* 返回最长子序列的长度 */  
int lis( int arr[], int n )  
{  
   int *lis, i, j, max = 0;  
   lis = (int*) malloc ( sizeof( int ) * n );  
   
   /* 将所有lis[i]初始化为1 */  
   for ( i = 0; i < n; i++ )  
      lis[i] = 1;  
      
   /* 计算 */  
   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;  
      
   /* 找出最大的长度 */  
   for ( i = 0; i < n; i++ )  
      if ( max < lis[i] )  
         max = lis[i];  
   
   /* 释放内存 */  
   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;  
}