基本介紹
- 中文名：最長不下降序列
- 定義：整個子序列單調不降，序列中最長的單調不降子序列
概念,算法,代碼,C++代碼,
概念
設有由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 的不下降序列。
算法
最長不下降序列nlogn算法：
算法分析：
設 A[t]表示序列中的第t個數，F[t]表示從1到t這一段中以t結尾的最長不下降子序列的長度，初始時設F [t] = 0(t = 1, 2,..., len(A))。則有動態規劃方程：F[t] = max{1, F[j] + 1} (j = 1, 2,..., t - 1, 且A[j] ＜ A[t])。
讓我們仔細考慮計算F[t]時的情況吧。假設有兩個元素A[x]和A[y]，滿足
(1)x ＜ y ＜ t
(2)A[x] ＜ A[y] ＜ A[t]
(3)F[x] = F[y]
此時，選擇F[x]和選擇F[y]都可以得到同樣的F[t]值，那么，在最長不下降子序列的這個位置中，應該選擇A[x]還是應該選擇A[y]呢？
很明顯，選擇A[x]比選擇A[y]要好。因為由於條件(2)，在A[x+1] ... A[t-1]這一段中，如果存在A[z]，A[x] ＜ A[z] ＜ A[y]，則與選擇A[y]相比，將會得到更長的不下降子序列。
再根據條件(3)，我們會得到一個啟示：根據F[]的值進行分類。對於F[]的每一個取值k，我們只需要保留滿足F[t] = k的所有A[t]中的最小值。設D[k]記錄這個值，即D[k] = min{A[t]} (F[t] = k)。
注意到D[]的兩個特點：
(1) D[k]的值是在整個計算過程中是單調不下降的。
(2) D[]的值是有序的，即D[1] ＜ D[2] ＜ D[3] ＜ ... ＜ D[n]。
利用D[]，我們可以得到另外一種計算最長不下降子序列長度的方法。設當前已經求出的最長不下降子序列長度為len。先判斷A[t]與D[len]。若A[t]＞=D[len]，則將A[t]接在D[len]後將得到一個更長的不下降子序列，len = len + 1， D[len] = A [t]；否則，在D[1]..D[len]中，找到最大的j，滿足D[j]＜=A[t]。此時將A[t]接在D[j]後將得到一個更長的不下降子序列，更新D[j+1]=A[t]。最後，len即為所要求的最長不下降子序列的長度。
在上述算法中，若使用樸素的順序查找在D[1]..D[len]查找，由於共有O(n)個元素需要計算，每次計算時的複雜度是O(n)，則整個算法的時間複雜度為O(n^2)，與原來的算法相比沒有任何進步。但是由於D[]的特點(2)，我們在D[]中查找時，可以使用二分查找高效地完成，則整個算法的時間複雜度下降為O(nlogn)，有了非常顯著的提高。需要注意的是，D[]在算法結束後記錄的並不是一個符合題意的最長不下降子序列！
代碼
代碼一
program nlogn;
var
d,a:array[0..100000]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)div2;
if d[mid]<=t then s:=mid+1 else w:=mid;
end;
min:=s;
end;
begin
readln(n);
for i:=1 to n do
read(a[i]);
readln;
len:=0;
d[0]:=-maxlongint;
for i:=1 to n do
begin
if a[i]>=d[len] then
begin
inc(len);
d[len]:=a[i];
end
else begin
k:=min(a[i]);
d[k]:=a[i];
end;
end;
writeln(len);
end.
代碼二
program max_rise(input,output);
const maxn=100;fname='q21.txt';
typet list=array[1..maxn,1..3]ofinteger;
vard:tlist;n:byte;
procedure init;
var
i:integer;
f:text;
begin
assign(f,fname);
reset(f);
readln(f,n);
fori:=1tondo
begin
read(f,d[i,1]);
d[i,2]:=1;
d[i,3]:=0
end;
close(f);
end;
procedure make;
var
i,j,p:byte;
l:integer;
begin
fori:=n-1 downto 1 do
begin
l:=0;p:=0;
for j:=i+1 to n do
if(d[i,1]<d[j,1])and(d[j,2]>l)then
begin
l:=d[j,2];
p:=j;
end;
if l>0 then
begin
d[i,2]:=l+1;
d[i,3]:=p;
end;
end;
end;
procedure output;
var
i,l,dmax:byte;
begin
write('source:');
for i:=1tondowrite(d[i,1]:5);
writeln;
dmax:=d[1,2];
l:=1;
for i:=2ton-1do
ifd[i,2]>dmaxthen
begin
dmax:=d[i,2];
l:=i;
end;
write('resultis:');
whilel<>0do
begin
write(d[l,1]:5);
l:=d[l,3];
end;
writeln;
writeln('maxlength=',dmax);
end;
begin
init;
make;
output;
end.
input:
10
318714
output:
source:31871410
resultis:3710122341
maxlength=6
代碼三
var
n,i,h,r,k,m:longint;
a,b:array[1..100000]oflongint;
begin
readln(n);
for i:=1 to n do read(a[i]);
k:=1;b[1]:=a[1];
for i:=2 to n do
if b[k]>a[i]then
begin
b[k+1]:=a[i];
inc(k);
end
else
begin
h:=1;r:=k;
while h<=r do
begin
m:=(h+r)div2;
if a[i]>b[m]then
r:=m-1
else h:=m+1;
end;
if a[i]>b[m] then b[m]:=a[i]
else b[m+1]:=a[i];
end;
writeln(k);
end.
C++代碼
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long d[100000],a[100000];
long long len,i,k,n;
long long min(long long t){
long long s,w,mid;
s=0;
w=len;
while(s<w){
mid=(s+w)/2;
if(d[mid]<=t)
s=mid+1;
else
w=mid;
}
return s;
}
int main(){
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
len=0;
d[0]=-29888888;//設一個非常小的數字
for(i=1;i<=n;i++){
if(a[i]>=d[len]){//放置數組
len++;
d[len]=a[i];
}else{
k=min(a[i]);
d[k]=a[i];
}
}
cout<<len<<endl;//輸出最長不下降子序列長度
return 0;
}
