問題描述

給定n個整數(shù)A1，A2,…,An，按從左到右的順序選出盡量多的整數(shù)，組成一個上升子序列。比如從序列1，6，2，3，7，5中，可以選出上升子序列1，2，3，5，也可以選出1，6，7，但前者更長。選出的上升子序列中相鄰元素不能相等。

問題分析

設(shè)d(i)為以編號i結(jié)尾的上升子序列的長度。那么對于上述序列1，6，2，3，7，5來說： d(1)=1 d(2)=2 d(3)=2(因為2<6,所以子序列為1,2) d(4)=3(子序列為1,2,3) d(5)=4(子序列為1,2,3,7) d(6)=4(子序列為1,2,3,5) 從上述對d(i)值的枚舉可以看出,d(i)=max{0,d(j)|j＜i,Aj＜Ai}+1=max{d(i)}(A為序列),很顯然可以看出，當(dāng)前算法的時間復(fù)雜度為O(n^2),那么能不能對這個算法進(jìn)行優(yōu)化呢，顯然是可以的.

算法優(yōu)化

假設(shè)已經(jīng)計算得到a，使得d(a)=t,且Aa為d值為t的序列中的最小值，那么在后續(xù)的序列中，顯然只要找到一個數(shù)字編號k，使得Ak＞Aa,那么就能滿足上升子序列的條件，且這樣不會丟失最優(yōu)解。證明如下： 設(shè)d(a)=d(b)=t,且Aa為d值為t的序列中的最小值，那么由假設(shè)可知Aa≤Ab,那么在后續(xù)序列中，找到一個數(shù)字編號k，因為Ak>Aa,但是因為Ak不一定大于Ab，所以如果舍棄Aa，顯然可能會舍棄最優(yōu)解，但如果舍棄Ab，確不一定會丟失最優(yōu)解。綜上，min{j|d(j)=i)為當(dāng)前選擇的最優(yōu)解. 現(xiàn)在有了上述的結(jié)論，那么我可以設(shè)g(i)為d值為i的最小狀態(tài)編號，那么一定有g(shù)(1)≤g(2)≤….≤g(n),所以現(xiàn)在只需要根據(jù)二分查找，找到一個數(shù)字編號k，使得g(k)≥Ai，更新d(i)=k,此時Ai＜g(k),而d(i)=k,所以更新g(k)=Ai.代碼如下:

這里寫代碼片 for(int i=1;i<=n;i++) g[i]=INF; for(int i=0;i＜n;i++){ int k=lower_bound(g+1,g+n+1,A[i]); d[i]=k; g[k]=A[i]; }