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

جستجوی زیرآرایه با بیشترین/کمترین مجموع

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

صورت مسئله

آرایه‌ای از اعداد $a[1 \ldots n]$ داده شده است. باید زیرآرایه‌ی $a[l \ldots r]$ با بیشترین مجموع را پیدا کنیم:

$$ \max_{ 1 \le l \le r \le n } \sum_{i=l}^{r} a[i].$$

برای مثال، اگر تمام اعداد در آرایه‌ی $a[]$ نامنفی بودند، آنگاه پاسخ، خود آرایه می‌بود. با این حال، راه حل زمانی غیربدیهی می‌شود که آرایه بتواند هم شامل اعداد مثبت و هم منفی باشد.

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

الگوریتم ۱

در اینجا یک الگوریتم تقریباً بدیهی را بررسی می‌کنیم. (در ادامه، الگوریتم دیگری را بررسی خواهیم کرد که رسیدن به آن کمی سخت‌تر است، اما پیاده‌سازی آن حتی کوتاه‌تر است.)

توضیح الگوریتم

الگوریتم بسیار ساده است.

برای راحتی، نمادگذاری زیر را معرفی می‌کنیم: $s[i] = \sum_{j=1}^{i} a[j]$. یعنی، آرایه‌ی $s[i]$ آرایه‌ای از مجموع‌های جزئی آرایه‌ی $a[]$ است. همچنین، $s[0] = 0$ قرار می‌دهیم.

حال بیایید روی اندیس $r = 1 \ldots n$ پیمایش کنیم و یاد بگیریم چگونه برای هر مقدار فعلی $r$، به سرعت $l$ بهینه را پیدا کنیم، که در آن بیشترین مجموع در زیرآرایه‌ی $[l, r]$ به دست می‌آید.

به طور رسمی، این بدان معناست که برای $r$ فعلی باید یک $l$ (که از $r$ بزرگتر نباشد) پیدا کنیم، به طوری که مقدار $s[r] - s[l-1]$ بیشینه باشد. پس از یک تبدیل بدیهی، می‌توانیم ببینیم که باید در آرایه‌ی $s[]$ کمترین مقدار را در بازه‌ی $[0, r-1]$ پیدا کنیم.

از اینجا، بلافاصله به یک راه حل می‌رسیم: ما به سادگی محل کمینه‌ی فعلی در آرایه‌ی $s[]$ را ذخیره می‌کنیم. با استفاده از این کمینه، اندیس بهینه‌ی فعلی $l$ را در $O(1)$ پیدا می‌کنیم و هنگام حرکت از اندیس فعلی $r$ به اندیس بعدی، به سادگی این کمینه را به‌روز می‌کنیم.

بدیهی است که این الگوریتم در $O(n)$ کار می‌کند و از نظر مجانبی بهینه است.

پیاده‌سازی

برای پیاده‌سازی آن، حتی نیازی به ذخیره‌ی صریح آرایه‌ی مجموع‌های جزئی $s[]$ نداریم — ما فقط به عنصر فعلی از آن نیاز خواهیم داشت.

پیاده‌سازی با آرایه‌های با اندیس ۰ ارائه شده است، نه با شماره‌گذاری از ۱ همانطور که در بالا توضیح داده شد.

ابتدا راه حلی را ارائه می‌دهیم که فقط پاسخ عددی را بدون پیدا کردن اندیس‌های بازه‌ی مورد نظر پیدا می‌کند:

int ans = a[0], sum = 0, min_sum = 0;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    ans = max(ans, sum - min_sum);
    min_sum = min(min_sum, sum);
}

حال نسخه‌ی کامل راه حل را ارائه می‌دهیم، که علاوه بر آن، مرزهای بازه‌ی مورد نظر را نیز پیدا می‌کند:

int ans = a[0], ans_l = 0, ans_r = 0;
int sum = 0, min_sum = 0, min_pos = -1;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    int cur = sum - min_sum;
    if (cur > ans) {
        ans = cur;
        ans_l = min_pos + 1;
        ans_r = r;
    }
    if (sum < min_sum) {
        min_sum = sum;
        min_pos = r;
    }
}

الگوریتم ۲

در اینجا الگوریتم متفاوتی را بررسی می‌کنیم. درک آن کمی دشوارتر است، اما از الگوریتم بالا زیباتر است و پیاده‌سازی آن کمی کوتاه‌تر است. این الگوریتم توسط Jay Kadane در سال ۱۹۸۴ پیشنهاد شد.

توضیح الگوریتم

خود الگوریتم به شرح زیر است. آرایه را پیمایش می‌کنیم و مجموع جزئی فعلی را در متغیری مانند $s$ جمع می‌کنیم. اگر در نقطه‌ای $s$ منفی شد، به سادگی $s=0$ قرار می‌دهیم. ادعا می‌شود که بیشترین مقداری که متغیر $s$ در طول الگوریتم به خود می‌گیرد، پاسخ مسئله خواهد بود.

اثبات:

اولین اندیسی را در نظر بگیرید که مجموع $s$ منفی می‌شود. این بدان معناست که با شروع از یک مجموع جزئی صفر، در نهایت به یک مجموع جزئی منفی می‌رسیم — بنابراین کل این پیشوند از آرایه، و همچنین هر پسوند آن، مجموعی منفی دارد. بنابراین، این زیرآرایه هرگز به مجموع جزئی هیچ زیرآرایه‌ای که این، پیشوند آن باشد کمکی نمی‌کند و می‌توان آن را به سادگی نادیده گرفت.

با این حال، این برای اثبات الگوریتم کافی نیست. در الگوریتم، ما در واقع در پیدا کردن پاسخ، تنها به بازه‌هایی محدود می‌شویم که بلافاصله بعد از مکان‌هایی شروع می‌شوند که در آنها $s<0$ شده است.

اما، در واقع، یک بازه‌ی دلخواه $[l, r]$ را در نظر بگیرید، و $l$ در چنین موقعیت «بحرانی» قرار ندارد (یعنی $l > p+1$، که $p$ آخرین موقعیتی است که در آن $s<0$ بوده است). از آنجایی که آخرین موقعیت بحرانی اکیداً قبل از $l-1$ است، نتیجه می‌شود که مجموع $a[p+1 \ldots l-1]$ نامنفی است. این بدان معناست که با انتقال $l$ به موقعیت $p+1$، ما پاسخ را افزایش خواهیم داد یا، در حالت‌های حدی، آن را تغییر نخواهیم داد.

به هر حال، مشخص می‌شود که هنگام جستجوی پاسخ، می‌توانید خود را فقط به بازه‌هایی محدود کنید که بلافاصله بعد از موقعیت‌هایی که در آنها $s<0$ ظاهر شده است، شروع می‌شوند. این صحت الگوریتم را اثبات می‌کند.

پیاده‌سازی

همانند الگوریتم ۱، ابتدا یک پیاده‌سازی ساده‌شده ارائه می‌دهیم که فقط به دنبال پاسخ عددی است بدون پیدا کردن مرزهای بازه‌ی مورد نظر:

int ans = a[0], sum = 0;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    ans = max(ans, sum);
    sum = max(sum, 0);
}

یک راه حل کامل، که اندیس‌های مرزهای بازه‌ی متناظر را حفظ می‌کند:

int ans = a[0], ans_l = 0, ans_r = 0;
int sum = 0, minus_pos = -1;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    if (sum > ans) {
        ans = sum;
        ans_l = minus_pos + 1;
        ans_r = r;
    }
    if (sum < 0) {
        sum = 0;
        minus_pos = r;
    }
}

مسائل مرتبط

پیدا کردن زیرآرایه‌ی بیشینه/کمینه با محدودیت

اگر شرایط مسئله محدودیت‌های اضافی بر بازه‌ی مورد نیاز $[l, r]$ اعمال کند (برای مثال، اینکه طول بازه $r-l+1$ باید در محدوده‌ی مشخصی باشد)، آنگاه الگوریتم توصیف‌شده به احتمال زیاد به راحتی برای این موارد قابل تعمیم است — به هر حال، مسئله همچنان پیدا کردن کمینه در آرایه‌ی $s[]$ با محدودیت‌های اضافی مشخص‌شده خواهد بود.

حالت دو بعدی مسئله: جستجوی زیرماتریس بیشینه/کمینه

مسئله‌ی توصیف‌شده در این مقاله به طور طبیعی به ابعاد بزرگتر تعمیم می‌یابد. برای مثال، در یک حالت دو بعدی، به جستجوی چنان زیرماتریسی $[l_1 \ldots r_1, l_2 \ldots r_2]$ از یک ماتریس داده شده تبدیل می‌شود، که بیشترین مجموع اعداد را در خود داشته باشد.

با استفاده از راه حل برای حالت یک بعدی، به راحتی می‌توان به یک راه حل در $O(n^3)$ برای حالت دو بعدی رسید: ما روی تمام مقادیر ممکن $l_1$ و $r_1$ پیمایش می‌کنیم و مجموع‌ها را از $l_1$ تا $r_1$ در هر سطر ماتریس محاسبه می‌کنیم. اکنون ما مسئله‌ی یک بعدی پیدا کردن اندیس‌های $l_2$ و $r_2$ را در این آرایه داریم، که می‌توان آن را در زمان خطی حل کرد.

الگوریتم‌های سریع‌تری برای حل این مسئله شناخته شده‌اند، اما آنها خیلی سریع‌تر از $O(n^3)$ نیستند و بسیار پیچیده هستند (آنقدر پیچیده که بسیاری از آنها به دلیل ثابت پنهان، برای تمام محدودیت‌های معقول از الگوریتم بدیهی ضعیف‌تر عمل می‌کنند). در حال حاضر، بهترین الگوریتم شناخته شده در زمان $O\left(n^3 \frac{ \log^3 \log n }{ \log^2 n} \right)$ کار می‌کند (T. Chan 2007 "More algorithms for all-pairs shortest paths in weighted graphs").

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

جستجوی زیرآرایه با میانگین بیشینه/کمینه

این مسئله در پیدا کردن چنان بازه‌ی $a[l, r]$ است، که مقدار میانگین آن بیشینه باشد:

$$ \max_{l \le r} \frac{ 1 }{ r-l+1 } \sum_{i=l}^{r} a[i].$$

البته، اگر هیچ شرط دیگری بر بازه‌ی مورد نیاز $[l, r]$ اعمال نشود، آنگاه راه حل همیشه یک بازه به طول ۱ در محل بزرگترین عنصر آرایه خواهد بود. این مسئله تنها زمانی معنا پیدا می‌کند که محدودیت‌های اضافی وجود داشته باشد (برای مثال، طول بازه‌ی مورد نظر از پایین محدود شده باشد).

در این حالت، ما از تکنیک استاندارد هنگام کار با مسائل مقدار میانگین استفاده می‌کنیم: ما مقدار میانگین بیشینه‌ی مورد نظر را با جستجوی دودویی (binary search) انتخاب خواهیم کرد.

برای انجام این کار، باید یاد بگیریم که چگونه زیرمسئله‌ی زیر را حل کنیم: عدد $x$ داده شده است، و ما باید بررسی کنیم که آیا زیرآرایه‌ای از آرایه‌ی $a[]$ (البته، با رعایت تمام محدودیت‌های اضافی مسئله) وجود دارد که مقدار میانگین آن بزرگتر از $x$ باشد.

برای حل این زیرمسئله، $x$ را از هر عنصر آرایه‌ی $a[]$ کم می‌کنیم. سپس زیرمسئله‌ی ما در واقع به این تبدیل می‌شود: که آیا زیرآرایه‌هایی با مجموع مثبت در این آرایه وجود دارد یا نه. و ما از قبل می‌دانیم چگونه این مسئله را حل کنیم.

بنابراین، ما به راه حلی با پیچیدگی مجانبی $O(T(n) \log W)$ رسیدیم، که در آن $W$ دقت مورد نیاز است، و $T(n)$ زمان حل زیروظیفه برای یک آرایه به طول $n$ است (که ممکن است بسته به محدودیت‌های اضافی خاص اعمال شده متفاوت باشد).

حل مسئله به صورت آنلاین

شرایط مسئله به شرح زیر است: یک آرایه از $n$ عدد و یک عدد $L$ داده شده است. پرس‌وجوهایی به شکل $(l,r)$ وجود دارد، و در پاسخ به هر پرس‌وجو، لازم است زیرآرایه‌ای از بازه‌ی $[l, r]$ به طولی که کمتر از $L$ نباشد، با بیشترین میانگین حسابی ممکن پیدا شود.

الگوریتم حل این مسئله بسیار پیچیده است. KADR (Yaroslav Tverdokhleb) الگوریتم خود را در فروم روسی توصیف کرده است.