最长递增子序列及应用

最长递增子序列

输入序列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;}