مسئله زیرآرایه بیشینه

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

مسئلهٔ زیرآرایهٔ بیشینه (به انگلیسی: maximum subarray problem) یک مسئله معروف در علوم رایانه است که در آن، هدف پیدا کردن زیرآرایه‌ای در یک آرایهٔ اعداد است که بزرگترین حاصل جمع را دارند (این آرایه دست کم باید شامل یک عدد مثبت باشد). به عنوان مثال، در آرایهٔ ۴ و ۵- و ۱ و ۲ و ۱- و ۴ و ۳- و ۱ و ۲- پاسخ مسئله عبارت است از زیرآرایهٔ ۱ و ۲ و ۱- و ۴ که حاصل جمعی برابر ۶ دارد.

این مسئله نخستین بار در سال ۱۹۷۷ توسط الف گرناندر ریاضی‌دان سوئدی و استاد دانشگاه براون و به عنوان یک مدل ساده برای تخمین درست‌نمایی بیشینه در الگوهای موجود در تصاویر دیجیتال ارائه شد. تنها پس از چند سال، جی کادان از دانشگاه کارنگی ملون موفق شد یک الگوریتم خطی برای حل این مسئله ارائه دهد.

پیوند به بیرون[ویرایش]