poj-2533
给出一个序列，求出这个序列的最长上升子序列。
序列A的上升子序列B定义如下：
B为A的子序列 B为严格递增序列Input 第一行包含一个整数n，表示给出序列的元素个数。
第二行包含n个整数，代表这个序列。 1 <= N <= 1000Output 输出给出序列的最长子序列的长度。
Sample Input 7 1 7 3 5 9 4 8Sample Output 4
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #include <iostream> using namespace std; #define N 1001 int a[N]; int l[N]; int main() { int i, n, j, max = 0; cin >> n; for (i = 0; i < n; i++) cin >> a[i]; memset(l, 0, sizeof(l)); l[0] = 1; for (i = 1; i < n; i++) { l[i] = 1; for (j = 0; j < i; j++) if (a[j] < a[i] && l[j] >= l[i]) l[i] = l[j] + 1; } //这里注意下，在求的时候l[i]的意思是：以a[i]结尾的最长上升子序列。 //但是，整个串的最长公共子序列可能不是以a[i]结尾。所以要遍历结尾，取最大值 for (i = 0; i < n; i++) if (l[i] > max) max = l[i]; cout << max << endl; return 0; }转载于:https://www.cnblogs.com/tttfu/p/11344915.html
