یک دنباله از اعداد به شما داده شده است و شما باید طول طولانیترین زیردنبالهی صعودی آن را پیدا کنید.
برای مثال دنبالهي ۹،۱،۶،۳،۷ را در نظر بگیرید. دنبالهی ۹،۶،۳ یک زیردنباله از این دنباله است اما صعودی نیست. دنبالهی ۱،۳،۶ یک دنبالهی صعودی است اما زیردنبالهی دنبالهی ما نیست. اما دنبالهی ۱،۶،۷ زیردنبالهی دنبالهی ما است و صعودی نیز هست. طول آن نیز سه است چون سه عضو دارد. در واقع این دنباله، طولانیترین زیردنبالهی صعودی دنبالهی ما است. پس جواب مسئله برای این دنباله برابر سه است.
بیایید سعی کنیم با کمک برنامهریزی پویا سوال را حل کنیم.
خانههای آرایهی دوبعدی d به اندازهی n+1 را به اینصورت تعریف میکنیم که مقدار di برابر طول طولانیترین زیردنبالهی صعودی است که عضو آخرش عضو i ام دنبالهی اولیه باشد. جواب مسئله، بزرگترین مقدار di به ازای n≥i≥1 است.
مقدار d0 را برای راحتی کار برابر صفر بگیرید. دنبالهی اولیه را نیز a مینامیم، پس ai یعنی مقدار عضو i ام دنباله.
میخواهیم مقدار di را محاسبه کنیم. عضو آخر آن که معلوم است. پس عضو یکی مانده به آخر آن هر مقداری میتواند باشد در صورتی که j<i و aj<ai . پس:
di=max
شبه کد (در این کد مقدار 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) است.
#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; }