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

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

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

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

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