编程之美---求数组中最长递增子序列LIS

对于那个O(nlgn)的算法实在用的不熟,大概能理解,不过还是欠火候,在此不贴了,以后再重新编辑

#include<stdio.h>#include<stdlib.h>#include<cstring>#include<assert.h>int LIS(int *a, int n){assert(NULL != a);int *dp = new int[n];memset(dp, 0, sizeof(dp));for(int i=0; i<n; i++){dp[i] = 1;for(int j=0; j<i; j++){if(a[i] > a[j] && (dp[j]+1>dp[i]))dp[i] = dp[j] + 1;}}int ret = dp[n-1];delete []dp;return ret;}void test(){int n = 0;while(scanf("%d", &n)!=EOF){if(n == 0) break;int *a = new int[n];for(int i=0; i<n; i++)scanf("%d", &a[i]);int ret = LIS(a, n);printf("%d\n", ret);delete []a;}}int main(){test();return 0;}