#include <stdio.h>
#include <windows.h>
# define MAX(a, b) ((a) > (b) ? (a) : (b))
int LIS(int * a, int n);
int main(void){
int a[] = {1,3,4,5,2,9};
int n = sizeof(a)/sizeof(int);
printf(“%d\n”, LIS(a, n));
system(“pause”);
return 0;
}
int LIS(int * a, int n){
if(NULL == a || 0 == n)
return 0;
int * dp = (int*)malloc(n*sizeof(int));//dp[i]是以a[i]结尾的最长上升子序列长度
int max = dp[0] = 1;
for(int i = 0; i < n; i++){
dp[i] = 1;
for(int j = 0; j < i; j++){
if(a[i] > a[j])
dp[i] = MAX(dp[i], dp[j] + 1);
}
max = MAX(max, dp[i]);
}
return max;
}