بیشینه‌ی زیرآرایه (کادان)
بازه‌ی پیوسته‌ای با بیشترین مجموع را در یک گذر پیدا می‌کند: هر وقت مجموع جاری منفی شد، آن را کنار می‌گذارد و از نو شروع می‌کند.
در آرایه‌ای از عددهای مثبت و منفی (مثلاً تغییرات روزانه‌ی قیمت)، بازه‌ی پیوسته‌ای پیدا کن که مجموعش بیشترین باشد.
ادامه‌ی توضیح ↓- زمان:
O(n) - حافظه:
O(1) - CLRS، بخش ۴.۱
شانزده تغییر روزانه‌ی قیمت؛ بهترین بازه a[7..10] با مجموع ۴۳ است.
def max_subarray(a):best = a[0]best_lo = 0best_hi = 0cur = a[0]cur_lo = 0for i in range(1, len(a)):if cur < 0:cur = a[i]cur_lo = ielse:cur = cur + a[i]if cur > best:best = curbest_lo = cur_lobest_hi = ireturn best, best_lo, best_hi
شروع اجرا
متغیرهای محلی
نارنجی = در همین گام عوض شد
a list
Call stack
- max_subarray()خط 1
رشد تعداد عملیات با اندازه‌ی ورودی
میانگین ۱۲ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.
- comparisons
- ورودی فعلی (n=16)
نمایش به شکل جدول
| n | comparisons |
|---|---|
| 4 | 6 |
| 6 | 10 |
| 8 | 14 |
| 10 | 18 |
| 12 | 22 |
| 14 | 26 |
| 16 | 30 |
توضیح
مسئله
در آرایه‌ای از عددهای مثبت و منفی (مثلاً تغییرات روزانه‌ی قیمت)، بازه‌ی پیوسته‌ای پیدا کن که مجموعش بیشترین باشد.
ایده‌ی کادان
برای هر خانه‌ی i، cur بیشترین مجموع زیرآرایه‌ای است که دقیقاً در i تمام می‌شود. این مقدار دو انتخاب دارد: یا زیرآرایه‌ی قبلی را با a[i] ادامه بده، یا از a[i] از نو شروع کن. اگر cur منفی است، ادامه دادنش فقط ضرر دارد، پس از نو شروع می‌کنیم. best بزرگ‌ترین cur دیده‌شده است.
هزینه
یک گذر: O(n) زمان و O(1) حافظه. CLRS همین مسئله را با تقسیم و حل در O(n log n) حل می‌کند؛ کادان نشان می‌دهد که با یک ایده‌ی برنامه‌ریزی پویا می‌شود خطی حلش کرد.
در trace به چه چیزی نگاه کنی
- نوار آبی بهترین بازه تا اینجاست؛ فلش
cur_loشروع اجرای جاری وiخانه‌ی جاری است. - در ورودی «شروع دوباره» ببین بعد از افت بزرگ،
cur_loجلو می‌پرد.