本篇博文為追憶曾經寫過的算法系列第三篇
溫故知新
題目重述
已知一個序列，由隨機數構成，求其最長單調子序列。
要求：單調分嚴格和不嚴格兩種情況，並分別求解並輸出一個最長單調子序列和所有符合要求的子序列。
問題分析
本題是求解有約束條件的子序列問題，可用動態規劃求解。由於本題是求解最長單調子序列的，包括求一個最長單調子序列和求解所有符合要求的序列，下面將按照這兩種情況討論算法復雜度。
求解一個最長單調子序列的算法復雜度
本題假設單調為遞增的情況，序列長度為N（任意大小），即序列S[N]。若采用直接搜索的方法，同時定義數組LP[N]記錄對應序列元素所在最長單調子序列中的位置。其算法思想如下：序列從S[1]開始(S[0])已經初始化），每遞增一個，判斷與之前的每個數值的大小，若S[i]>
S[j](j=”)且LP[i]<=LP
[j]+1，則更新LP[i]為LP[j]+1。這樣保證了每個元素歸類到自身所滿足的最長子序列當中，但此算法的復雜度為O(n^2)。
通過對第二層循環，即確定新加進的元素其所在最長子序列的位置，可改進搜索策略，將復雜度降低為O(nlogn)。基本思想是：定義數組Len[N+1]，第0個元素空閒，第j(j>0)個位置存儲所有長度為j的子序列中最後元素的最小值，這樣可以保證當前序列為最長序列且保持局部最優。當對新添加的元素S[i]進行判別時，采用二分搜索法在Len數組中搜索元素的位置，由於Len一直保持升序排列，且搜索到其所在的位置後，取代比他大的元素，從而成為那個長度的序列最後元素最小，其搜索復雜度為O(logn)。在算上第一層循環的O(n)，所以復雜度為O(nlogn)。通過LP[N]和S[N]可循環求解出一個最長單調子序列，復雜度為O(n)。所以，總復雜度為O(nlogn)。
求解所有最長單調子序列的復雜度
求解所有最長單調子序列，其和2.1中的唯一不同在於求解輸出所有最長單調子序列，而求解LP[N]和MaxLen的復雜度同2.1中的分析，最好方法的復雜度為O(nlogn)。輸出所有最長單調子序列（設其復雜度為O(T)）和上述過程是並列而非嵌套，所以總的復雜度為。
而T的求解很容易，通過分析可以發現，其中第一個n指循環LP[N]得到最長子序列的起始位置，而k指所有最長子序列的個數，取小於號是因為最長序列的起始點總是小於n的。
綜上可以得到，求解所有最長單調子序列的復雜度為，其中k的取值為[0,n]。即極端情況下為O(n^2)，這裡之所以討論是想強調無限長序列下有限個最長單調子序列的思想。
算法思想與實現
a.定義S[N]，LP[N]，Len[N+1]三個數組，其分別是序列本身，序列元素對應的最長子序列位置記錄，長度為i的子序列最末元素的最小值。其中S[N]隨機生成，Len[0]閒置；
b.初始化LP[0]為1，S[N]從i=1開始循環至N-1；K用於記錄Len的最大值，即目前搜索到的最長子序列長度，其初始值為K=1；若S[i]>Len[K]
(注：若非嚴格則是“>=”)，即下一個元素的值大於最長子序列最後元素的值，則直接將S[i]放在Len[++K]的位置；若S[i]<=Len[K]，則進入步驟c；
c.調用函數k
= fn_InsertPos()，並執行如下操作： Len[k]=S[i]; LP[i] = k; LP[i]仍記錄了S[i]所在的最長子序列位置，有利於序列的輸出；fn_InsertPos()采用二分查找法，但和常規的查找條件不同，其算法復雜度為O(logn)；
d.完成S[i]的搜索後，Len所記錄的k值即為最長單調子序列的長度，此時可通過LP[N
]數組的記錄求出一個最長子序列，即從後向前遍歷LP[N]，用輔助數組P[N]記錄子序列，k記錄當前需要存入的子序列長度，當LP[i]==k且S[i]=”)，將S[i]存入P[--k]，直至k==0，具體過程可參見函數void
fn_OutPutLMS(int Pos )，其算法復雜度為；
e.要輸出所有最長單調子序列，則需要確定所有最長子序列的末尾元素所在的位置，這個容易實現，即定義數組C[N]，遍歷LP[N]並記錄值為MaxLen的元素的位置。然後一次調用voidfn_OutPutLMS(int
Pos )，復雜度為。
程序實現
/*-----------------------------------------------------------------
* 最長單調子序列問題
* -----------------------------------------------------------------
* By Gu Jinjin SEU
* 求解最長單調子序列，分嚴格和不嚴格兩種情況
* 這裡以單調遞增為例
* Time ： 2012/11/28-29 Weather：rainy
*/
#include
#include
#include
using std::cout;
using std::endl;
// define
#define N 5000
// S[N]-序列，LP[N]-序列元素在最長子序列中的位置
// Len[N+1]-用於記錄i長度的所有單調子序列末尾元素最小值
int S[N],LP[N],Len[N+1];
// 記錄最長單調子序列長度
int MaxLen;
// 函數聲明
void fn_RandNum();
int fn_InsertPos(int Si, int K);
int fn_GetLMS_Len();
void fn_OutPutInitList();
void fn_OutPutLMS(int Pos);
void fn_GetAllLMSes();
/*-----------------------------------------------------------------
* void main( void )
* -----------------------------------------------------------------
* 主函數
*/
void main()
{
clock_t t_start,t_end;
fn_RandNum();
t_start=clock();
MaxLen = fn_GetLMS_Len();
t_end=clock();
cout<<"Inital List:"<high,則說明搜索到
while(low <= high)
{
if(low > high)break;
else if(Len[mid]Len[lmn])
{
Len[++lmn]=S[i];
LP[i]=lmn;
}
else
{
k = fn_InsertPos(S[i],lmn);
Len[k] = S[i];
LP[i] = k;
}
}
return(lmn);
}
/*-----------------------------------------------------------------
* void fn_OutPutInitSeq( ... )
* -----------------------------------------------------------------
* 輸出原始數列
*/
void fn_OutPutInitList()
{
cout<<"S"<<'\t'<<"LP"<<'\t'<<"Len"<=0; i--)
{
if(LP[i] == k && S[i]< P[k])P[--k]=S[i];
}
// OutPut LMS
if(k==0)
{
for(int i=0; i=MaxLen-1; i--)
{
if(LP[i]==MaxLen){ C[k]=i; k++;}
}
for(int i=0;i
結果（N取20的時候，其中數組為隨機函數生成）
