最长递增子序列及应用
最长递增子序列
输入序列X：5,9,4,8,3,7,6,10，则输出该序列的最长递增子序列的长度为3，其中一个最长递增子序列为5,9,10.
两种思路(基于动态规划方法求解)：
思路1 将序列X递增排序为序列Y：3,4,5,6,7,8,9,10，原问题就转化成求X，Y两个序列的最长公共子序列问题.（本文不提供具体解法）
思路2 设f[i]表示以下标i结尾的最长递增子序列的长度
则： f[0] = 1 for i = 0
f[i] = max{max{f[j]+1 | 0=< j < i 且X[j] <= X[i]} , 1} for 0 < i < n
设pre[i]表示以下标i结尾的最长递增子序列中下标i对应的元素的前驱元素对应的下标(-1表示没有前驱)
例：5,9,4,8,3,7,6,10
f[0] = 1 pre[0] = -1 5(序列)
f[1] = 2 pre[1] = 0 5,9
f[2] = 1 pre[2] = -1 4
f[3] = 2 pre[3] = 0 5,8
f[4] = 1 pre[4] = -1 3
f[5] = 2 pre[5] = 0 5,7
f[6] = 2 pre[6] = 0 5,6
f[7] = 3 pre[7] = 1 5,9,10
则最长递增子序列的长度为3，其中一个最长递增子序列为5,9,10（通过pre构造）.
具体代码实现如下：
/************************************************************************//* Input: (ht,wt) (65,100) (70,150) (56,90) (75,90) (60,95) (68,110) Output: longest tower 6 (56,90) (60,95) (65,100) (68,110) (70,150) (75,190) *//************************************************************************/struct Person{int m_ht; //身高int m_wt; //体重};//比较算子，以身高优先比较，在身高相同的情况下比较体重int compare(const void* p1, const void* p2){int x1 = ((Person*)p1)->m_ht;int y1 = ((Person*)p1)->m_wt;int x2 = ((Person*)p2)->m_ht;int y2 = ((Person*)p2)->m_wt;if(x1 > x2){return 1;}else if(x1 == x2){return y1-y2 >= 0 ? !!(y1-y2) : -1;}else{return -1;}}int getLargestNumOfPeople(Person* pPerson, int n, Person* pRes){if(pPerson == NULL || pRes == NULL || n <= 0) return -1;int* pWt = new int[n];qsort(pPerson,n,sizeof(Person),compare);for(int i = 0; i < n; ++i){pWt[i] = pPerson[i].m_wt;}int* nPreIndx = new int[n];int index;int largestN = maxIncreaseSubSequence(pWt,n,nPreIndx,index);int* pMaxSub = MISubSequence(nPreIndx,index);int j = 0;for(i = pMaxSub[0]; i > 0; --i,++j){pRes[j] = pPerson[pMaxSub[i]];}delete[] pMaxSub;return largestN;}