Question

dynamic_programming

תהא a1,,ana_1, \ldots, a_n סדרת מספרים.

  1. הציעו אלגוריתם המוצא תת סדרה עוקבת מונוטונית לא יורדת ארוכה ביותר של הסדרה.
  2. הציעו אלגוריתם המוצא תת סדרה (לאו דווקא עוקבת) מונוטונית לא יורדת ארוכה ביותר של הסדרה.
1

Answers

1. נסמן ב-f(i)f(i) את אורך תת הסדרה העוקבת הארוכה ביותר שמתחילה ב-aia_i ונשים לב שמתקיימת נוסחת הנסיגה הבאה:

f(i)={1+f(i+1)ai+1ai1otherwise f(i) = \begin{cases} 1 + f(i + 1) & a_{i + 1} \geq a_i \\ 1 & \text{otherwise} \end{cases}

ניתן לחשב את f(i)f(i) במערך בגודל nn מהערכים הגדולים לנמוכים.בהינתן מערך כזה אנחנו מחפשים את maxif(i)\max_i f(i).

סיבוכיות: חישוב המערך ניתן לעשות בזמן לינארי וכן את מציאת הערך המקסימלי.

2. נסמן ב-f(i)f(i) את האורך המקסימלי של תת סדרה (לאו דווקא עוקבת) של ai,,ana_i, \dots, a_n ונשים לב שמתקיימת נוסחת הנסיגה הבאה:

f(i)=max{f(i+1)1+maxj>i:ajaif(j) f(i) = \max \begin{cases} f(i + 1) \\ 1 + \displaystyle{\max_{j > i : a_j \geq a_i}}f(j) \end{cases}

אנחנו רוצים למצוא את f(1)f(1) וניתן לעשות לחשב זאת במערך בגודל nn.

סיבוכיות: חישוב ערך בודד במערך ניתן לעשות בזמן O(n)O(n) ואת חישוב המערך כולו בזמן O(n2)O(n^2).

1
Feedback