2014
02-26

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

/* 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;
}


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

/* 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;
}

ACM之家原创：链接：

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();}.