最长递增子序列的另外一种C语言实现代码

//file lmis.c #include "lmis.h" #include <stdio.h> #include <stdlib.h> #include <math.h> #include <time.h> void init(int size) { a = (int*)malloc ((size) * sizeof (int)); if(!a) { printf("memory alloc error!"); return; } b = (int*)malloc ((size+1) * sizeof (int)); if(!b) { printf("memory alloc error!"); return; } newRandArray(a, size); } void newRandArray(int a[], int nCount) { int i,address; int *b; b = (int*)malloc ((nCount) * sizeof (int)); if(!b) { printf("memory alloc error!"); return; } for (i = 0; i < nCount; i++)// 初始化临时数组 b[i] = i+1; srand((unsigned)time(NULL));//设置随机数产生种子 for(i =nCount-1; i>=0; i--) { address = rand() % (i+1);// 产生随机下标 a[i]=b[address];// 保存到第i个单元中 if (address != i) b[address] = b[i]; } } void LMIS_Find(int a[], int b[], int size) { int i, j, k, s, m, e; b[0] = -1; b[1] = a[0]; length = 1; j=0; for(i=1; i<size; i++) { s = 0; e = length; while(s <= e) { m = (s + e)/2; if(b[m] < a[i]) { s = m+1; } else { e = m-1; } } if(s>length) { b[s] = a[i]; a[length++] = a[i]; } else { b[s] = a[i]; j++; if(j == length) { for(k=0;k<length;k++) { a[k] = b[k+1]; } j=0; } } } } void Print_LMIS(int a[], int len) { int i; printf("\n最长递增子序列的长度："); printf("%d",len); printf("\n最长递增子序列:\n"); for(i=0; i<len; i++) { printf("%d ",a[i]); } } void FreeArray() { free(a); free(b); length = 0; }