数组最大上升子序列解法
#include <stdio.h>#define N 9//O(nlogn)/**该方法可求最大上升子序列同时，可求最大不下降子序列如{2,1,1,4}这种连续两个元素相等的序列，最大不下降子序列为{1,1,4}*/void lis1(int *a){int i,j=0,temp,b[N],low,mid,high;b[0]=a[0];for(i=1;i<N;i++){if(a[i]>=b[j]){b[++j]=a[i];}else{low=0;high=j;while(low<=high){mid=(low+high)/2;if(a[i]>b[mid]){low=mid+1;}else{high=mid-1;}}b[low]=a[i];}}printf("LIS=%d",j+1);}//O(n^2)/**该方法在这一版本中不能求最大不下降子序列同时也不是把下面代码中a[i]>a[j]修改为a[i]>=a[j]就可以这么简单原因是跟这一解法的动态规划的状态转移方程有关，具体是怎么关系，没理解透*/void lis2(int *a){int i,j=0,temp,b[N],max;b[0]=1;//初始化，以a[0]结尾的最长递增子序列长度为1 for(i=1;i<N;i++) { b[i]=1;//b[i]最小值为1 for(j=0;j<i;j++) if(a[i]>a[j]&&b[j]+1>b[i]) b[i]=b[j]+1; } for(max=i=0;i<N;i++){//求出整个数列的最长递增子序列的长度if(b[i]>max) max=b[i]; } printf("max=%d",max);}void main(){int a[]={3,1,4,2,5,7,6,8,9};lis1(a);lis2(a);}