最長不下降序列

len len d[len

設有由n個不相同的整數組成的數列，記為:a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j)
例如3，18，7，14，10，12，23，41，16，24。
若存在i1<i2<i3< … < ie 且有a(i1)<a(i2)< … <a(ie)則稱為長度為e的不下降序列。如上例中3，18，23，24就是一個長度為4的不下降序列，同時也有3，7，10，12，16，24長度為6的不下降序列。
下面是求一個最長不下降序列的pascal代碼
program max_rise(input,output);
const maxn=100;fname="q21.txt";
type Tlist=array&#91;1..maxn,1..3&#93; of integer;
var d:tlist;n:byte;
procedure init;
var
i:integer;
f:text;
begin
assign(f,fname);
reset(f);
readln(f,n);
for i:=1 to n do
begin
read(f,d&#91;i,1&#93;);
d&#91;i,2&#93;:=1;
d&#91;i,3&#93;:=0
end;
close(f);
end;
procedure make;
var
i,j,p:byte;
l:integer;
begin
for i:=n-1 downto 1 do
begin
l:=0;p:=0;
for j:=i+1 to n do
if (d&#91;i,1&#93;<d&#91;j,1&#93;) and (d&#91;j,2&#93;>l) then
begin
l:=d&#91;j,2&#93;;
p:=j;
end;
if l>0 then
begin
d&#91;i,2&#93;:=l+1;
d&#91;i,3&#93;:=p;
end;
end;
end;
procedure output;
var
i,l,DMAX:byte;
begin
write('source:');
for i:=1 to n do write(d&#91;i,1&#93;:5);
writeln;
dmax:=d&#91;1,2&#93;;
l:=1;
for i:=2 to n-1 do
if d&#91;i,2&#93;>dmax then
begin
dmax:=d&#91;i,2&#93;;
l:=i;
end;
write('result is: ');
while l<>0 do
begin
write(d&#91;l,1&#93;:5);
l:=d&#91;l,3&#93;;
end;
writeln;
writeln('max length=",dmax);
end;
begin
init;
make;
output;
end.
input:
10
3 18 7 14 10 12 23 41 16 24
output:
source: 3 18 7 14 10 12 23 41 16 24
result is: 3 7 10 12 23 41
max length = 6
最長不下降序列nlogn算法：
算法分析：
設 A&#91;t&#93;表示序列中的第t個數，F&#91;t&#93;表示從1到t這一段中以t結尾的最長上升子序列的長度，初始時設F &#91;t&#93; = 0(t = 1, 2, ..., len(A))。則有動態規劃方程：F&#91;t&#93; = max{1, F&#91;j&#93; + 1} (j = 1, 2, ..., t - 1, 且A&#91;j&#93; < A&#91;t&#93;)。
現在，我們仔細考慮計算F&#91;t&#93;時的情況。假設有兩個元素A&#91;x&#93;和A&#91;y&#93;，滿足
(1)x < y < t
(2)A&#91;x&#93; < A&#91;y&#93; < A&#91;t&#93;
(3)F&#91;x&#93; = F&#91;y&#93;
此時，選擇F&#91;x&#93;和選擇F&#91;y&#93;都可以得到同樣的F&#91;t&#93;值，那么，在最長上升子序列的這個位置中，應該選擇A&#91;x&#93;還是應該選擇A&#91;y&#93;呢？
很明顯，選擇A&#91;x&#93;比選擇A&#91;y&#93;要好。因為由於條件(2)，在A&#91;x+1&#93; ... A&#91;t-1&#93;這一段中，如果存在A&#91;z&#93;，A&#91;x&#93; < A&#91;z&#93; < a&#91;y&#93;，則與選擇A&#91;y&#93;相比，將會得到更長的上升子序列。
再根據條件(3)，我們會得到一個啟示：根據F&#91;&#93;的值進行分類。對於F&#91;&#93;的每一個取值k，我們只需要保留滿足F&#91;t&#93; = k的所有A&#91;t&#93;中的最小值。設D&#91;k&#93;記錄這個值，即D&#91;k&#93; = min{A&#91;t&#93;} (F&#91;t&#93; = k)。
注意到D&#91;&#93;的兩個特點：
(1)　D&#91;k&#93;的值是在整個計算過程中是單調不上升的。
(2)　D&#91;&#93;的值是有序的，即D&#91;1&#93; < D&#91;2&#93; < D&#91;3&#93; < ... < D&#91;n&#93;。
利 用D&#91;&#93;，我們可以得到另外一種計算最長上升子序列長度的方法。設當前已經求出的最長上升子序列長度為len。先判斷A&#91;t&#93;與D&#91;len&#93;。若A &#91;t&#93; > D&#91;len&#93;，則將A&#91;t&#93;接在D&#91;len&#93;後將得到一個更長的上升子序列，len = len + 1， D&#91;len&#93; = A &#91;t&#93;；否則，在D&#91;1&#93;..D&#91;len&#93;中，找到最大的j，滿足D&#91;j&#93; < A&#91;t&#93;。令k = j + 1，則有A &#91;t&#93; <= D&#91;k&#93;，將A&#91;t&#93;接在D&#91;j&#93;後將得到一個更長的上升子序列，更新D&#91;k&#93; = A&#91;t&#93;。最後，len即為所要求的最長上 升子序列的長度。
在 上述算法中，若使用樸素的順序查找在D&#91;1&#93;..D&#91;len&#93;查找，由於共有O(n)個元素需要計算，每次計算時的複雜度是O(n)，則整個算法的 時間複雜度為O(n^2)，與原來的算法相比沒有任何進步。但是由於D&#91;&#93;的特點(2)，我們在D&#91;&#93;中查找時，可以使用二分查找高效地完成，則整個算法 的時間複雜度下降為O(nlogn)，有了非常顯著的提高。需要注意的是，D&#91;&#93;在算法結束後記錄的並不是一個符合題意的最長上升子序列！
pascal代碼：
program nlogn;
var
d,a:array&#91;0..100000&#93; of longint;
len,i,k,n:longint;
Function min(t:longint):longint;
var s,w,mid:longint;
begin
s:=0;w:=len;
while s<w do begin
mid:=(s+w)div 2;
if d&#91;mid&#93;<t then s:=mid+1 else w:=mid;
end;
min:=s;
end;
begin
readln(n);
for i:=1 to n do read(a&#91;i&#93;);
readln;
len:=0;
d&#91;0&#93;:=-maxlongint;
for i:=1 to n do begin
if a&#91;i&#93;>d&#91;len&#93; then begin
inc(len);
d&#91;len&#93;:=a&#91;i&#93;;
end else begin
k:=min(a&#91;i&#93;);
if d&#91;k&#93;>a&#91;i&#93; then d&#91;k&#93;:=a&#91;i&#93;;
end;
end;
writeln(len);
end.