طولانی‌ترین زیردنباله‌ی صعودی

تعریف

یک دنباله از اعداد به شما داده شده است و شما باید طول طولانی‌ترین زیردنباله‌ی صعودی آن را پیدا کنید.
برای مثال دنباله‌ي ۹،۱،۶،۳،۷ را در نظر بگیرید. دنباله‌ی ۹،۶،۳ یک زیردنباله از این دنباله است اما صعودی نیست. دنباله‌ی ۱،۳،۶ یک دنباله‌ی صعودی است اما زیردنباله‌ی دنباله‌ی ما نیست. اما دنباله‌ی ۱،۶،۷ زیردنباله‌ی دنباله‌ی ما است و صعودی نیز هست. طول آن نیز سه است چون سه عضو دارد. در واقع این دنباله، طولانی‌ترین زیردنباله‌ی صعودی دنباله‌ی ما است. پس جواب مسئله برای این دنباله برابر سه است.

الگوریتم اولیه

بیایید سعی کنیم با کمک برنامه‌ریزی پویا سوال را حل کنیم.
خانه‌های آرایه‌ی دوبعدی $d$ به اندازه‌ی $n+1$ را به اینصورت تعریف می‌کنیم که مقدار $d_i$ برابر طول طولانی‌ترین زیردنباله‌ی صعودی است که عضو آخرش عضو $i$ ام دنباله‌ی اولیه باشد. جواب مسئله، بزرگ‌ترین مقدار $d_i$ به ازای $n \geq i \geq 1$ است.
مقدار $d_0$ را برای راحتی کار برابر صفر بگیرید. دنباله‌ی اولیه را نیز $a$ می‌نامیم، پس $a_i$ یعنی مقدار عضو $i$ ام دنباله. می‌خواهیم مقدار $d_i$ را محاسبه کنیم. عضو آخر آن که معلوم است. پس عضو یکی مانده به آخر آن هر مقداری می‌تواند باشد در صورتی که $j < i$ و $a_j < a_i$ . پس: $d_i = \max_{\substack{j>i\\a_j<a_i}}{(d_j + 1)}$ شبه کد (در این کد مقدار $d_0$ را تعریف نکردیم و آرایه‌های $d$ و $a$ از صفر شروع می‌شوند):

for i from 0 to n-1
	d[i] = 1
	for j from 0 to i-1
		if d[j] < d[i]
			d[i] = max( d[i] , d[j] + 1 )

پیچیدگی‌ الگوریتم اولیه

حافظه از $O(n)$ است. و هر به روز رسانی نیز از $O(n)$ پس پیچیدگی زمانی از $O(n^2)$ است.

الگوریتم سریع‌تر

این سوال الگوریتمی سریع‌تر و کمی پیچیده‌تر هم دارد که توضیح دادن آن کمی سخت است. پس در این قسمت لطفا کمی بیشتر دقت کنید.
فرض کنید بخواهیم تمام زیردنباله‌های صعودی را یک جوری نگه داریم تا در به روز رسانی خانه‌های جدول‌مان کمک کند. از هر زیردنباله، برای ما فقط عضو آخر و طول دنباله برای ما مهم است. اگر هم چند دنباله با طول‌های برابر داشته باشیم، آن دنباله‌ای که عضو آخرش کوچکتر باشد، بهتر است. به این هم دقت کنید که اگر یک زیردنباله‌ی صعودی به طول $i>1$ داشته باشیم حتما یک زیردنباله صعودی به طول $i-1$ نیز داریم.
پس اگر بزرگ‌ترین طولی که تا الان پیدا کرده‌ایم $k \leq n$ باشد (طول زیردنباله‌ها از خود دنباله بزرگ‌تر نمی‌شود)، $k$ مقدار نیز داریم که هرکدام کمترین مقدار عضو آخر یک زیر دنباله به همین اندازه اند. آن‌ها را می‌توانیم در یک آرایه به نام $last$ به طول حداکثر $n$ قرار دهیم. اگر دقت کنید، می‌بینید که این آرایه باید اکیدا صعودی باشد. چون اگر زیردنباله‌ای که $v = last_i$ با شرط $i>1$ عضو انتها‌یی آن است را در نظر بگیرید، عضو یکی مانده به آخری، حتما از $v$ کوچکتر است و خودش انتهای زیردنباله‌ای به طول $i-1$ است.
حال اگر این آرایه را در هنگام محاسبه‌ی $d_i$ در اختیار داشته باشیم، می‌توانیم این مقدار را به صورت زیر محاسبه کنیم: $d_i = \max_{\substack{ a_i > last_j \\ j \leq k }}(j+1)$ و چون آرایه‌ی $last$ اکیدا صعودی است، می‌توانیم این مقدار را با یک جستجوی دودویی پیدا کنیم. همچنین برای این که آرایه‌ی $last$ را بعد از اضافه کردن عضو $i$ ام به روز رسانی کنیم، فقط کافی است که خانه‌ی $last_{j+1}$ را اگر وجود داشت برابر $\min(last_{j+1},a_i)$ قرار دهیم وگرنه آن را برابر $a_i$ قرار دهیم (چرا؟).
شبه کد ( $inf$ یعنی مقدار بی‌نهایت، یا حداقل مقداری که از تمام اعضای آرایه‌ی $a$ بزرگ‌تر باشد):

last = {inf}
last[0] = 0

for i from 0 to n-1
	j = bin_search( last , 0 , n , a[i] )
	d[i] = j+1
	last[j+1] = min( last[j+1] , a[i] )

پیچیدگی‌ الگوریتم سریع‌تر

حافظه که هنوز از $O(n)$ است. به روز رسانی هم در $O(lg n)$ انجام می‌گیرد. پس پیچیدگی زمانی از $O(n.lg n)$ است.

پیاده‌سازی الگوریتم سریع‌تر

‌‌LIS.cpp

#include <iostream>
#include <algorithm>
using namespace std;
 
const int INF = 1<<30; // 2 ^ 30
const int MAXN = 100*1000;
 
int a[MAXN+10];
int d[MAXN+10];
int last[MAXN+10];
 
int main(){
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	for(int i=0; i<n; i++)
		cin >> a[i];
 
	for(int i=0; i<n; i++)
		last[i] = INF;
	last[0] = 0;
 
	int best = 0;
 
	for(int i=0; i<n; i++){
		int j = lower_bound(last, last+n, a[i]) - last - 1;
		d[i] = j+1;
		last[j+1] = min( last[j+1] , a[i] );
 
		best = max( best , d[i] );
	}
 
	cout << best << endl;
 
	return 0;
}

−فهرست مندرجات