本文共 2133 字，大约阅读时间需要 7 分钟。
#include #include #include int min(int arr[],int len);int max(int arr[], int len);void pr_arr(int arr[], int len);void pr_mostIncreaseList(int arr[], int MaxCount[], int len, int curi, int prei,int curCount);//方法一：用MaxCount[]来保存当前位置为最后结点的 最长序列数int mostIncreaseList(int arr[], int len){ int MaxCount[len]; int i, k; for (i = 0; i < len; i++) { MaxCount[i] = 1; for (k = 0; k < i; k++) { if (arr[i] > arr[k] && MaxCount[i] < MaxCount[k] + 1) MaxCount[i] = MaxCount[k] + 1; } } /*pr_arr(MaxCount, len); printf("\n"); pr_mostIncreaseList(arr, MaxCount, len, 0, -1, 1); printf("\n");*/ return max(MaxCount, len);}//方法二：MaxV[i]表示序列数为i 的各个递增子序列最大元素的最小值int mostIncreaseList2(int arr[],int len){ int MaxV[len+1]; int MaxCount[len]; int nMaxList=1; int i,k; for(i=0;i =0;k--) { if(arr[i] > MaxV[k]) { MaxCount[i]=k+1; break; } }//如果之上的for循环查找 变成二分查找，会快点。 if(MaxCount[i] > nMaxList) { nMaxList=MaxCount[i]; MaxV[MaxCount[i]]=arr[i]; } else { if(arr[i]>MaxV[k] && arr[i] < MaxV[k+1]) { MaxV[k+1]=arr[i]; } } } printf("\n"); pr_arr(MaxV,nMaxList); printf("\n"); pr_arr(MaxCount,len); return nMaxList;}int min(int arr[],int len){ int i=0; int nMin=arr[0]; assert(len >0); for(i=1;i arr[i]) nMin=arr[i]; } return nMin;}int max(int arr[], int len){ int i = 0, m; if (len < 1) return -1; m = arr[0]; for (i = 1; i < len; i++) if (m < arr[i]) m = arr[i]; return m;}//打印数组中的元素void pr_arr(int arr[], int len){ int i = 0; for (i = 0; i < len; i++) printf("%d ", arr[i]); printf("\n");}//打印其中一条 递增序列 测试用void pr_mostIncreaseList(int arr[], int MaxCount[], int len, int curi, int prei, int curCount){ if (curi >= len) return; if (curCount == MaxCount[curi] && curi < len) { if (prei == -1 || arr[curi] > arr[prei]) { printf("%d ", arr[curi]); prei = curi; ++curCount; } } pr_mostIncreaseList(arr, MaxCount, len, curi + 1, prei, curCount);}int main(void){ int a[] ={ -1, 1, -2, 2, 0, -3, 4, -5, 6, -7, 9 }; printf("%d \n", mostIncreaseList(a, sizeof(a) / sizeof(int))); printf("%d \n", mostIncreaseList2(a, sizeof(a) / sizeof(int))); return 0;}
转载地址：http://jicci.baihongyu.com/