問(wèn)題描述

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

問(wèn)題分析

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

算法優(yōu)化

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

這里寫(xiě)代碼片 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]; }