תת־מערך מקסימלי (הפרד ומשול)

מוצא את תת־המערך בעל הסכום המקסימלי על ידי חלוקת המערך ושילוב סביב נקודת האמצע.

שלב 1 מתוך 35

תת־המערך המקסימלי (הפרד ומשול): פצל את המערך בנקודת האמצע, בצע רקורסיה על כל חצי, מצא את תת־המערך החוצה המקסימלי, והחזר את הטוב מבין השלושה.

▶אלגוריתם

MaxSubarrayDC(arr, lo, hi):
if lo == hi: return arr[lo]
mid = (lo + hi) / 2
left  = MaxSubarrayDC(arr, lo, mid)
right = MaxSubarrayDC(arr, mid+1, hi)
cross = MaxCrossing(arr, lo, mid, hi)
return max(left, right, cross)
// maximum subarray found

בכל רמה: מצא את המקסימום בחצי השמאלי, בחצי הימני, ובחוצה את נקודת האמצע. החזר את הטוב מבין השלושה. זמן O(n log n), מקום מחסנית O(log n).

-2

-3

-1

-5

תת־בעיה פעילה

תת־מערך חוצה

התוצאה הטובה ביותר

1 / 35מהירות