مسئله بیشینه زیرآرایه چیست؟
در علوم کامپیوتر، مسئله بیشینه مجموع زیرآرایه (Maximum sum subarray problem) که با نام مسئله بیشینه مجموع بخش نیز شناخته میشود، وظیفه پیدا کردن یک زیرآرایه پیوسته با بزرگترین مجموع مقادیر را درون یک آرایه یکبعدی دادهشده از اعداد بر عهده دارد. این مسئله را میتوان با پیچیدگی زمانی O(n) و پیچیدگی فضایی O(1) حل کرد.
به زبان دقیق، هدف یافتن اندیسهای i و j است تا مجموع مقادیر بین آنها بیشترین مقدار ممکن را بگیرد. البته در برخی تعریفها، زیرآرایه خالی نیز مجاز شمرده میشود که طبق قرارداد، مجموع آن برابر صفر است. هر عدد در آرایه ورودی میتواند مثبت، منفی یا صفر باشد.
برای مثال، در آرایه [−2, 1, −3, 4, −1, 2, 1, −5, 4]، زیرآرایه پیوستهای که بیشترین مجموع را دارد [4, −1, 2, 1] است که مجموع آن ۶ میشود.
ویژگیهای مسئله
- اگر آرایه فقط شامل اعداد نامنفی باشد، مسئله بدیهی است؛ خود آرایه کامل، بیشینه زیرآرایه محسوب میشود.
- اگر آرایه فقط شامل اعداد نامثبت باشد، راهحل، زیرآرایهای به طول ۱ است که بیشترین مقدار آرایه را در خود دارد (یا اگر مجاز باشد، زیرآرایه خالی).
- ممکن است چندین زیرآرایه متفاوت، مجموع بیشینه یکسانی داشته باشند.
با وجود اینکه این مسئله با تکنیکهای مختلفی نظیر روش brute force، تقسیم و غلبه، برنامهنویسی پویا و کوتاهترین مسیر قابل حل است، الگوریتم سادهای با نام الگوریتم کادین (Kadane's algorithm) به شکلی کارآمد آن را با یک عبور ساده حل میکند.
تاریخچه
اولف گرنلندر (Ulf Grenander) در سال ۱۹۷۷ مسئله بیشینه زیرآرایه را به عنوان مدلی سادهشده برای تخمین بیشینه درستنمایی الگوها در تصاویر دیجیتال مطرح کرد. او در پی یافتن یک زیرآرایه مستطیلی با بیشترین مجموع در یک آرایه دوبعدی اعداد حقیقی بود. از آنجا که الگوریتم brute force برای مسئله دوبعدی زمان بسیار طولانی O(n^6) را صرف میکرد، گرنلندر مسئله یکبعدی را برای درک بهتر ساختار آن پیشنهاد داد.
او ابتدا الگوریتمی با زمان O(n^2) ارائه داد. وقتی مایکل شیموس با مسئله آشنا شد، در یک شب الگوریتم تقسیم و غلبهای با زمان O(n log n) را طراحی کرد. مدت کوتاهی بعد، جی کادین در سمیناری در دانشگاه کارنگی ملون با مسئله آشنا شد و در کمتر از یک دقیقه، الگوریتمی با زمان O(n) را ابداع کرد که سریعترین حالت ممکن است.
کاربردها
مسئله بیشینه زیرآرایه در حوزههای متعددی کاربرد دارد:
- تحلیل توالی ژنوم: برای شناسایی بخشهای زیستی مهم در توالیهای پروتئین مانند بخشهای حفاظتشده، مناطق غنی از GC، تکرارهای پشت سر هم و نواحی با بار بالا.
- بینایی ماشین: برای تشخیص روشنترین ناحیه در تصاویر بیتمپ استفاده میشود.
الگوریتم کادین
الگوریتم کادین آرایه ورودی را از چپ به راست بررسی میکند. در هر مرحله، زیرآرایهای با بیشترین مجموع را که در موقعیت فعلی خاتمه مییابد، محاسبه کرده و در متغیر current_sum نگه میدارد. همچنین بیشترین مجموع کل را در متغیر best_sum ذخیره میکند.
حالت بدون اجازه زیرآرایه خالی
اگر آرایه ورودی هیچ عنصر مثبتی نداشته باشد، خروجی برابر بزرگترین عنصر (نزدیکترین عدد به صفر) خواهد بود. این مسئله را میتوان با کد پایتون زیر پیادهسازی کرد:
def max_subarray(numbers):
best_sum = -infinity
current_sum = 0
for x in numbers:
current_sum = max(x, current_sum + x)
best_sum = max(best_sum, current_sum)
return best_sum
حالت با اجازه زیرآرایه خالی
نسخه اصلی الگوریتم کادین حالتی است که زیرآرایه خالی مجاز باشد. اگر ورودی عنصر مثبتی نداشته باشد، خروجی صفر خواهد بود. برای این حالت، مقدار اولیه best_sum صفر قرار داده میشود و در حلقه، current_sum به صورت max(0, current_sum + x) بهروزرسانی میشود.
محاسبه موقعیت زیرآرایه
الگوریتم را به راحتی میتوان تغییر داد تا علاوه بر مجموع، اندیسهای شروع و پایان زیرآرایه بیشینه را نیز ذخیره کند. از آنجا که این الگوریتم از ساختارهای بهینه (بیشینه زیرآرایه هر موقعیت بر اساس موقعیت قبلی محاسبه میشود) استفاده میکند، یک نمونه ساده از برنامهنویسی پویا به شمار میرود.
پیچیدگی
پیچیدگی زمانی الگوریتم کادین O(n) و پیچیدگی فضایی آن O(1) است.
تعمیمها
مسائل مشابهی برای آرایههای با ابعاد بالاتر مطرح میشوند، اما راهحلهای آنها پیچیدهتر است. همچنین روشهایی برای یافتن k زیرآرایه با بیشترین مجموع در یک آرایه یکبعدی در زمان بهینه ارائه شده است.