最长递增子序列

设L = <a1,a2,...an>是n个不同的实数的序列，L的递增子序列是这样一个子序列：

Lin = <ak1, ak2, ..., akm>, 其中k1 < k2 < ... < km且ak1 < ak2 < ... < akm。

求最大的m，即求最长递增子序列的长度。

使用动态规划解决：

令f[i] 表示长度为i的递增子序列中末尾的元素

len[i] 表示a[1]...a[i]的最长递增子序列的长度

那么如何求len[i]呢？

找出max{j, f[j] < a[i], j = 1...len[i-1] }， 若所有f[j] >= a[i]，则令j = 0，

然后len[i] = j+1； 更新f[len[i]] = a[i]， 由于f[i]是递增的，所以求

max{j, f[j] < a[i], j = 1...len[i] }时可以用二分查找，整个过程算法复杂度为O(n*logn)

 

 

#include <stdio.h>
#include <string.h>

#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

#define N 20
#define max(a,b) (a) > (b) ? (a) : (b)

int f[N];

void find(int *a, int n)
{
	int 	i, s, t, m, len;

	f[1] = a[1];
	len = 1;
	for (i = 2; i <= n; i++) {
		s = 1; t = len;
		while (s <= t) {
			m = (s+t)/2;
			if (f[m] < a[i]) {
				s = m+1;
			}
			else {
				t = m-1;
			}
		}
		f[t+1] = a[i];
		printf("f[%d] = %d\n", t+1, f[t+1]);
		len = max(t+1, len);
	}
	printf("%d\n", len);
}

int main()
{
	int a[] = {0,7,8,3,2,1,1};

	find(a,6);
	return 0;
}

评论

1 楼 ph4nut 2011-05-04  

算法，这个有点像是数学知识