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

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

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

پیوند به بیرون

• الگوریتم کادان
• الگوریتم‌های مکعبی، مربعی و خطی برای حل مسئله زیرآرایهٔ بیشینه به زبان جاوا
• حل مسئله زیرآرایهٔ بیشینه به زبان پایتون