پرش به محتویات

بلندترین زیررشتهٔ صعودی

آرایه‌ای با $n$ عدد به ما داده شده است: $a[0 \dots n-1]$. مسئله، یافتن بلندترین زیررشتهٔ اکیداً صعودی در $a$ است.

به طور رسمی، ما به دنبال بلندترین دنباله از اندیس‌های $i_1, \dots i_k$ هستیم به طوری که:

$$i_1 < i_2 < \dots < i_k,\quad a[i_1] < a[i_2] < \dots < a[i_k]$$

در این مقاله چندین الگوریتم برای حل این مسئله را بررسی می‌کنیم. همچنین مسائل دیگری را که می‌توان به این مسئله کاهش داد، مورد بحث قرار خواهیم داد.

راه حل $O(n^2)$ با برنامه‌نویسی پویا {data-toc-label="راه حل $O(n^2)$ با برنامه‌نویسی پویا"}

برنامه‌نویسی پویا (Dynamic programming) یک تکنیک بسیار کلی است که امکان حل دستهٔ بزرگی از مسائل را فراهم می‌کند. در اینجا ما این تکنیک را برای مسئلهٔ خاص خودمان به کار می‌بریم.

ابتدا تنها به دنبال طول بلندترین زیررشتهٔ صعودی خواهیم بود و بعداً یاد می‌گیریم که چگونه خود زیررشته را بازیابی کنیم.

پیدا کردن طول

برای انجام این کار، آرایهٔ $d[0 \dots n-1]$ را تعریف می‌کنیم که در آن $d[i]$ طول بلندترین زیررشتهٔ صعودی است که به عنصر با اندیس $i$ ختم می‌شود.

Example

$$\begin{array}{ll} a &= \{8, 3, 4, 6, 5, 2, 0, 7, 9, 1\} \\ d &= \{1, 1, 2, 3, 3, 1, 1, 4, 5, 2\} \end{array}$$

بلندترین زیررشتهٔ صعودی که به اندیس ۴ ختم می‌شود، $\{3, 4, 5\}$ با طول ۳ است، بلندترین زیررشته که به اندیس ۸ ختم می‌شود یا $\{3, 4, 5, 7, 9\}$ یا $\{3, 4, 6, 7, 9\}$ است که هر دو طول ۵ دارند و بلندترین زیررشته که به اندیس ۹ ختم می‌شود $\{0, 1\}$ با طول ۲ است.

ما این آرایه را به تدریج محاسبه می‌کنیم: ابتدا $d[0]$، سپس $d[1]$ و به همین ترتیب. پس از محاسبهٔ این آرایه، پاسخ مسئله، بیشترین مقدار در آرایهٔ $d[]$ خواهد بود.

بنابراین، فرض کنید اندیس کنونی $i$ باشد. یعنی، ما می‌خواهیم مقدار $d[i]$ را محاسبه کنیم و تمام مقادیر قبلی $d[0], \dots, d[i-1]$ از قبل مشخص هستند. در این صورت دو گزینه وجود دارد:

  • $d[i] = 1$: زیررشتهٔ مورد نظر تنها از عنصر $a[i]$ تشکیل شده است.

  • $d[i] > 1$: زیررشته به $a[i]$ ختم می‌شود و درست قبل از آن، عددی مانند $a[j]$ با شرایط $j < i$ و $a[j] < a[i]$ قرار دارد.

    به راحتی می‌توان دید که زیررشتهٔ منتهی به $a[j]$ خود یکی از بلندترین زیررشته‌های صعودی است که به $a[j]$ ختم می‌شود. عدد $a[i]$ فقط آن بلندترین زیررشتهٔ صعودی را با یک عدد گسترش می‌دهد.

    بنابراین، می‌توانیم روی تمام $j < i$ با شرط $a[j] < a[i]$ پیمایش کنیم و بلندترین دنباله‌ای را که با اضافه کردن $a[i]$ به بلندترین زیررشتهٔ صعودی منتهی به $a[j]$ به دست می‌آید، در نظر بگیریم. بلندترین زیررشتهٔ صعودی منتهی به $a[j]$ طولی برابر $d[j]$ دارد، گسترش آن با یک عنصر، طولی برابر $d[j] + 1$ می‌دهد.

    $$d[i] = \max_{\substack{j < i \\\\ a[j] < a[i]}} \left(d[j] + 1\right)$$

اگر این دو حالت را ترکیب کنیم، به پاسخ نهایی برای $d[i]$ می‌رسیم:

$$d[i] = \max\left(1, \max_{\substack{j < i \\\\ a[j] < a[i]}} \left(d[j] + 1\right)\right)$$

پیاده‌سازی

در اینجا پیاده‌سازی الگوریتم توصیف‌شده در بالا آمده است که طول بلندترین زیررشتهٔ صعودی را محاسبه می‌کند.

int lis(vector<int> const& a) {
    int n = a.size();
    vector<int> d(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i])
                d[i] = max(d[i], d[j] + 1);
        }
    }

    int ans = d[0];
    for (int i = 1; i < n; i++) {
        ans = max(ans, d[i]);
    }
    return ans;
}

بازیابی زیررشته

تا اینجا فقط یاد گرفتیم چگونه طول زیررشته را پیدا کنیم، اما نه اینکه چگونه خود زیررشته را بیابیم.

برای اینکه بتوانیم زیررشته را بازیابی کنیم، یک آرایهٔ کمکی اضافی $p[0 \dots n-1]$ ایجاد می‌کنیم که آن را در کنار آرایهٔ $d[]$ محاسبه خواهیم کرد. $p[i]$ اندیس $j$ یعنی عنصر یکی مانده به آخر در بلندترین زیررشتهٔ صعودی منتهی به $i$ خواهد بود. به عبارت دیگر، اندیس $p[i]$ همان اندیس $j$ است که در آن بیشترین مقدار $d[i]$ به دست آمده است. این آرایه کمکی $p[]$ به نوعی به "اجداد" (ancestors) اشاره می‌کند.

سپس برای به دست آوردن زیررشته، فقط از اندیس $i$ با $d[i]$ ماکسیمم شروع می‌کنیم و اجداد را دنبال می‌کنیم تا کل زیررشته را استنتاج کنیم، یعنی تا زمانی که به عنصری با $d[i]=1$ برسیم.

پیاده‌سازی بازیابی

کد بخش‌های قبلی را کمی تغییر خواهیم داد. آرایهٔ $p[]$ را در کنار $d[]$ محاسبه می‌کنیم و پس از آن زیررشته را به دست می‌آوریم.

برای راحتی، در ابتدا به اجداد مقدار $p[i] = -1$ را اختصاص می‌دهیم. برای عناصری با $d[i]=1$ مقدار اجداد $-1$ باقی می‌ماند که برای بازیابی زیررشته کمی راحت‌تر خواهد بود.

vector<int> lis(vector<int> const& a) {
    int n = a.size();
    vector<int> d(n, 1), p(n, -1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && d[i] < d[j] + 1) {
                d[i] = d[j] + 1;
                p[i] = j;
            }
        }
    }

    int ans = d[0], pos = 0;
    for (int i = 1; i < n; i++) {
        if (d[i] > ans) {
            ans = d[i];
            pos = i;
        }
    }

    vector<int> subseq;
    while (pos != -1) {
        subseq.push_back(a[pos]);
        pos = p[pos];
    }
    reverse(subseq.begin(), subseq.end());
    return subseq;
}

روش جایگزین برای بازیابی زیررشته

همچنین امکان بازیابی زیررشته بدون آرایهٔ کمکی $p[]$ نیز وجود دارد. می‌توانیم به سادگی مقدار فعلی $d[i]$ را دوباره محاسبه کنیم و همچنین ببینیم که چگونه به ماکسیمم رسیده‌ایم.

این روش منجر به کدی کمی طولانی‌تر می‌شود، اما در عوض مقداری حافظه صرفه‌جویی می‌کنیم.

راه حل $O(n \log n)$ با برنامه‌نویسی پویا و جستجوی دودویی {data-toc-label="راه حل $O(n \log n)$ با برنامه‌نویسی پویا و جستجوی دودویی"}

برای به دست آوردن راه حل سریع‌تر برای مسئله، یک راه حل برنامه‌نویسی پویای متفاوت می‌سازیم که در $O(n^2)$ اجرا می‌شود و سپس آن را به $O(n \log n)$ بهبود می‌بخشیم.

از آرایهٔ برنامه‌نویسی پویای $d[0 \dots n]$ استفاده خواهیم کرد. این بار $d[l]$ به عنصر $a[i]$ یا به پیشوندی از آرایه مرتبط نیست. $d[l]$ کوچکترین عنصری خواهد بود که یک زیررشتهٔ صعودی به طول $l$ به آن ختم می‌شود.

در ابتدا فرض می‌کنیم $d[0] = -\infty$ و برای تمام طول‌های دیگر $d[l] = \infty$ است.

ما دوباره اعداد را به تدریج پردازش می‌کنیم، ابتدا $a[0]$، سپس $a[1]$ و غیره، و در هر مرحله آرایهٔ $d[]$ را به گونه‌ای حفظ می‌کنیم که به‌روز باشد.

Example

با توجه به آرایهٔ $a = \{8, 3, 4, 6, 5, 2, 0, 7, 9, 1\}$، در اینجا تمام پیشوندهای آن و آرایهٔ برنامه‌نویسی پویای مربوطه آمده است. توجه داشته باشید که مقادیر آرایه همیشه در انتها تغییر نمی‌کنند.

$$ \begin{array}{ll} \text{prefix} = \{\} &\quad d = \{-\infty, \infty, \dots\}\\ \text{prefix} = \{8\} &\quad d = \{-\infty, 8, \infty, \dots\}\\ \text{prefix} = \{8, 3\} &\quad d = \{-\infty, 3, \infty, \dots\}\\ \text{prefix} = \{8, 3, 4\} &\quad d = \{-\infty, 3, 4, \infty, \dots\}\\ \text{prefix} = \{8, 3, 4, 6\} &\quad d = \{-\infty, 3, 4, 6, \infty, \dots\}\\ \text{prefix} = \{8, 3, 4, 6, 5\} &\quad d = \{-\infty, 3, 4, 5, \infty, \dots\}\\ \text{prefix} = \{8, 3, 4, 6, 5, 2\} &\quad d = \{-\infty, 2, 4, 5, \infty, \dots \}\\ \text{prefix} = \{8, 3, 4, 6, 5, 2, 0\} &\quad d = \{-\infty, 0, 4, 5, \infty, \dots \}\\ \text{prefix} = \{8, 3, 4, 6, 5, 2, 0, 7\} &\quad d = \{-\infty, 0, 4, 5, 7, \infty, \dots \}\\ \text{prefix} = \{8, 3, 4, 6, 5, 2, 0, 7, 9\} &\quad d = \{-\infty, 0, 4, 5, 7, 9, \infty, \dots \}\\ \text{prefix} = \{8, 3, 4, 6, 5, 2, 0, 7, 9, 1\} &\quad d = \{-\infty, 0, 1, 5, 7, 9, \infty, \dots \}\\ \end{array} $$

هنگامی که $a[i]$ را پردازش می‌کنیم، می‌توانیم از خود بپرسیم. تحت چه شرایطی باید عدد فعلی $a[i]$ را در آرایهٔ $d[0 \dots n]$ بنویسیم؟

ما $d[l] = a[i]$ قرار می‌دهیم، اگر یک زیررشتهٔ صعودی به طول $l$ وجود داشته باشد که به $a[i]$ ختم شود، و هیچ زیررشتهٔ صعودی دیگری به طول $l$ نباشد که به عنصری کوچکتر ختم شود. مشابه رویکرد قبلی، اگر عدد $a[i]$ را از زیررشتهٔ صعودی به طول $l$ حذف کنیم، یک زیررشتهٔ صعودی دیگر به طول $l-1$ به دست می‌آوریم. بنابراین ما می‌خواهیم یک زیررشتهٔ صعودی به طول $l-1$ را با عدد $a[i]$ گسترش دهیم، و بدیهی است که زیررشتهٔ صعودی به طول $l-1$ که با کوچکترین عنصر پایان می‌یابد بهترین عملکرد را خواهد داشت، به عبارت دیگر دنباله‌ای به طول $l-1$ که به عنصر $d[l-1]$ ختم می‌شود.

یک زیررشتهٔ صعودی به طول $l - 1$ وجود دارد که می‌توانیم آن را با عدد $a[i]$ گسترش دهیم، دقیقاً اگر $d[l-1] < a[i]$ باشد. بنابراین می‌توانیم روی هر طول $l$ پیمایش کنیم و با بررسی معیار، ببینیم آیا می‌توانیم یک زیررشتهٔ صعودی به طول $l - 1$ را گسترش دهیم.

علاوه بر این، باید بررسی کنیم که آیا قبلاً یک زیررشتهٔ صعودی به طول $l$ با عددی کوچکتر در انتها پیدا کرده‌ایم یا نه. بنابراین تنها در صورتی به‌روزرسانی می‌کنیم که $a[i] < d[l]$ باشد.

پس از پردازش تمام عناصر $a[]$، طول زیررشتهٔ مورد نظر، بزرگترین $l$ است که $d[l] < \infty$ باشد.

int lis(vector<int> const& a) {
    int n = a.size();
    const int INF = 1e9;
    vector<int> d(n+1, INF);
    d[0] = -INF;

    for (int i = 0; i < n; i++) {
        for (int l = 1; l <= n; l++) {
            if (d[l-1] < a[i] && a[i] < d[l])
                d[l] = a[i];
        }
    }

    int ans = 0;
    for (int l = 0; l <= n; l++) {
        if (d[l] < INF)
            ans = l;
    }
    return ans;
}

اکنون دو مشاهدهٔ مهم را بیان می‌کنیم.

  1. آرایهٔ $d$ همیشه مرتب خواهد بود: $d[l-1] < d[l]$ برای تمام $i = 1 \dots n$.

    این موضوع بدیهی است، زیرا می‌توانید فقط آخرین عنصر را از زیررشتهٔ صعودی به طول $l$ حذف کنید و یک زیررشتهٔ صعودی به طول $l-1$ با عدد پایانی کوچکتر به دست آورید.

  2. عنصر $a[i]$ حداکثر یک مقدار $d[l]$ را به‌روزرسانی خواهد کرد.

    این موضوع مستقیماً از پیاده‌سازی بالا نتیجه می‌شود. فقط یک مکان در آرایه می‌تواند با شرط $d[l-1] < a[i] < d[l]$ وجود داشته باشد.

بنابراین می‌توانیم این عنصر را در آرایهٔ $d[]$ با استفاده از جستجوی دودویی (binary search) در زمان $O(\log n)$ پیدا کنیم. در واقع، می‌توانیم به سادگی در آرایهٔ $d[]$ به دنبال اولین عددی بگردیم که اکیداً بزرگتر از $a[i]$ است و سعی کنیم این عنصر را به همان روش پیاده‌سازی بالا به‌روزرسانی کنیم.

پیاده‌سازی

این کار پیاده‌سازی بهبودیافتهٔ $O(n \log n)$ را به ما می‌دهد:

int lis(vector<int> const& a) {
    int n = a.size();
    const int INF = 1e9;
    vector<int> d(n+1, INF);
    d[0] = -INF;

    for (int i = 0; i < n; i++) {
        int l = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
        if (d[l-1] < a[i] && a[i] < d[l])
            d[l] = a[i];
    }

    int ans = 0;
    for (int l = 0; l <= n; l++) {
        if (d[l] < INF)
            ans = l;
    }
    return ans;
}

بازیابی زیررشته

بازیابی زیررشته با استفاده از این رویکرد نیز امکان‌پذیر است. این بار باید دو آرایهٔ کمکی را نگهداری کنیم. یکی که اندیس عناصر در $d[]$ را به ما می‌گوید. و دوباره باید آرایه‌ای از "اجداد" $p[i]$ ایجاد کنیم. $p[i]$ اندیس عنصر قبلی برای زیررشتهٔ بهینهٔ منتهی به عنصر $i$ خواهد بود.

نگهداری این دو آرایه در حین پیمایش آرایهٔ $a[]$ و در کنار محاسبات $d[]$ آسان است. و در پایان، بازیابی زیررشتهٔ مورد نظر با استفاده از این آرایه‌ها دشوار نیست.

راه حل $O(n \log n)$ با ساختمان داده‌ها {data-toc-label="راه حل $O(n \log n)$ با ساختمان داده‌ها"}

به جای روش بالا برای محاسبهٔ بلندترین زیررشتهٔ صعودی در $O(n \log n)$، می‌توانیم مسئله را به روش دیگری نیز حل کنیم: با استفاده از چند ساختمان داده ساده.

بیایید به روش اول بازگردیم. به یاد بیاورید که برای محاسبهٔ $d[i]$، به دنبال ماکسیمم مقدار $d[j] + 1$ در میان تمام $j$هایی هستیم که $j < i$ و $a[j] < a[i]$ است.

بنابراین، اگر یک آرایهٔ اضافی $t[]$ را به گونه‌ای تعریف کنیم که

$$t[a[i]] = d[i],$$

آنگاه مسئلهٔ محاسبهٔ مقدار $d[i]$ معادل یافتن بیشترین مقدار در یک پیشوند از آرایهٔ $t[]$ است:

$$d[i] = \max\left(t[0 \dots a[i] - 1]\right) + 1$$

مسئلهٔ یافتن ماکسیمم یک پیشوند از آرایه‌ای (که تغییر می‌کند) یک مسئلهٔ استاندارد است که می‌تواند با ساختمان داده‌های مختلفی حل شود. به عنوان مثال، می‌توانیم از درخت بازه‌ای (Segment tree) یا درخت فنویک (Fenwick tree) استفاده کنیم.

این روش به وضوح کاستی‌هایی دارد: از نظر طول و پیچیدگی پیاده‌سازی، این رویکرد بدتر از روشی است که از جستجوی دودویی استفاده می‌کند. علاوه بر این، اگر اعداد ورودی $a[i]$ به خصوص بزرگ باشند، باید از ترفندهایی مانند فشرده‌سازی اعداد (یعنی شماره‌گذاری مجدد آنها از $0$ تا $n-1$) یا استفاده از یک درخت بازه‌ای پویا (dynamic segment tree) (فقط شاخه‌هایی از درخت را که مهم هستند ایجاد کنیم) استفاده کنیم. در غیر این صورت، مصرف حافظه بسیار بالا خواهد بود.

از سوی دیگر، این روش مزایایی نیز دارد: با این روش نیازی نیست به هیچ‌یک از ویژگی‌های پیچیده در راه حل برنامه‌نویسی پویا فکر کنید. و این رویکرد به ما امکان می‌دهد که مسئله را به راحتی تعمیم دهیم (به ادامه مطلب مراجعه کنید).

مسائل مرتبط

در اینجا چندین مسئله وجود دارد که ارتباط نزدیکی با مسئلهٔ یافتن بلندترین زیررشتهٔ صعودی دارند.

بلندترین زیررشتهٔ غیر نزولی

این در واقع تقریباً همان مسئله است. فقط حالا مجاز است که از اعداد یکسان در زیررشته استفاده شود.

راه حل نیز در اصل تقریباً یکسان است. فقط باید علامت‌های نامساوی را تغییر دهیم و اصلاح جزئی در جستجوی دودویی انجام دهیم.

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

می‌توانیم از اولین روش مورد بحث، یا نسخهٔ $O(n^2)$ یا نسخهٔ با استفاده از ساختمان داده‌ها، استفاده کنیم. فقط باید به طور اضافی ذخیره کنیم که به چند طریق می‌توان به بلندترین زیررشتهٔ صعودی منتهی به اندیس $i$ (با طول $d[i]$) رسید.

تعداد راه‌های تشکیل یک بلندترین زیررشتهٔ صعودی که به $a[i]$ ختم می‌شود، برابر است با مجموع تعداد راه‌های تمام زیررشته‌های منتهی به $j$ (با $j<i$ و $a[j]<a[i]$) که طول آن‌ها یعنی $d[j]$، ماکسیمم ممکن ($d[i]-1$) است. ممکن است چندین چنین $j$ وجود داشته باشد، بنابراین باید تعداد راه‌های همه آنها را با هم جمع کنیم.

با استفاده از درخت بازه‌ای (Segment tree) این رویکرد نیز می‌تواند در $O(n \log n)$ پیاده‌سازی شود.

استفاده از رویکرد جستجوی دودویی برای این کار ممکن نیست.

کوچکترین تعداد زیررشته‌های غیر صعودی برای پوشش یک دنباله

برای یک آرایهٔ داده شده با $n$ عدد $a[0 \dots n - 1]$، باید اعداد را با کمترین تعداد رنگ، رنگ‌آمیزی کنیم، به طوری که هر رنگ یک زیررشتهٔ غیر صعودی تشکیل دهد.

برای حل این مسئله، متوجه می‌شویم که حداقل تعداد رنگ‌های مورد نیاز برابر با طول بلندترین زیررشتهٔ صعودی است.

اثبات: باید دوگانگی (duality) این دو مسئله را اثبات کنیم.

فرض کنید $x$ طول بلندترین زیررشتهٔ صعودی باشد و $y$ کمترین تعداد زیررشته‌های غیر صعودی باشد که یک پوشش را تشکیل می‌دهند. باید ثابت کنیم که $x = y$.

واضح است که $y < x$ ممکن نیست، زیرا اگر $x$ عنصر اکیداً صعودی داشته باشیم، هیچ دوتای آنها نمی‌توانند بخشی از یک زیررشتهٔ غیر صعودی باشند. بنابراین $y \ge x$ است.

اکنون با برهان خلف نشان می‌دهیم که $y > x$ ممکن نیست. فرض کنید $y > x$ باشد. سپس هر مجموعه بهینه از $y$ زیررشتهٔ غیر صعودی را در نظر می‌گیریم. ما این مجموعه را به روش زیر تبدیل می‌کنیم: تا زمانی که دو زیررشته وجود داشته باشند که اولی قبل از دومی شروع شود و دنبالهٔ اول با عددی بزرگتر یا مساوی با عدد شروع دنباله دوم آغاز شود، آنگاه این عدد شروع را جدا کرده و به ابتدای دنباله دوم متصل می‌کنیم. پس از تعداد متناهی مرحله، $y$ زیررشته خواهیم داشت و اعداد شروع آنها یک زیررشتهٔ صعودی به طول $y$ تشکیل خواهند داد. از آنجا که فرض کردیم $y > x$، به تناقض رسیده‌ایم.

بنابراین نتیجه می‌شود که $y = x$.

بازیابی دنباله‌ها: پارتیشن‌بندی مورد نظر دنباله به زیررشته‌ها را می‌توان به صورت حریصانه انجام داد. یعنی، از چپ به راست حرکت کرده و عدد فعلی را به آن زیررشته‌ای اختصاص دهید که با کوچکترین عددی که بزرگتر یا مساوی عدد فعلی است، پایان می‌یابد.

مسائل تمرینی