[动态规划-1] 最长递增子序列-Longest Increasing Subsequence
问题描述：求一个一维数组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<stdio.h>#include<stdlib.h> /* 返回最长子序列的长度 */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;}