問題描述

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

問題分析

設d(i)為以編號i結尾的上升子序列的長度。那么對于上述序列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為序列),很顯然可以看出，當前算法的時間復雜度為O(n^2),那么能不能對這個算法進行優化呢，顯然是可以的.

算法優化

假設已經計算得到a，使得d(a)=t,且Aa為d值為t的序列中的最小值，那么在后續的序列中，顯然只要找到一個數字編號k，使得Ak＞Aa,那么就能滿足上升子序列的條件，且這樣不會丟失最優解。證明如下： 設d(a)=d(b)=t,且Aa為d值為t的序列中的最小值，那么由假設可知Aa≤Ab,那么在后續序列中，找到一個數字編號k，因為Ak>Aa,但是因為Ak不一定大于Ab，所以如果舍棄Aa，顯然可能會舍棄最優解，但如果舍棄Ab，確不一定會丟失最優解。綜上，min{j|d(j)=i)為當前選擇的最優解. 現在有了上述的結論，那么我可以設g(i)為d值為i的最小狀態編號，那么一定有g(1)≤g(2)≤….≤g(n),所以現在只需要根據二分查找，找到一個數字編號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]; }