תת־מערך מקסימלי

מוצא את תת־המערך הרציף בעל הסכום הגדול ביותר בעזרת אלגוריתם קדאן.

מערך קלט

-21-34-121-54

שלב 1 מתוך 11

תת־מערך מקסימלי (קדאן): מצא את תת־המערך הרציף בעל הסכום הגדול ביותר. dp[i] = סכום תת־המערך המקסימלי המסתיים באינדקס i.

▶אלגוריתם

MaxSubarray(arr):
dp[0] = arr[0]; maxSum = dp[0]
for i = 1 to n−1:
dp[i] = max(dp[i−1]+arr[i], arr[i])
maxSum = max(maxSum, dp[i])
return maxSum

מקרא

תא dp נוכחי

תלויות

תת־מערך אופטימלי

מחושב

dp[i] = סכום תת־המערך המקסימלי המסתיים באינדקס i. הארך אם dp[i−1] + arr[i] > arr[i], אחרת התחל מחדש.

1 / 11מהירות