מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/פתרון תת-מחרוזת עולה ארוכה ביותר ברדוקציה/תשובה

הפונקציה Convert(X) פשוט תחזיר את המערך ממויין בסדר עולה. (אם נשתמש במיון מיזוג, אז הסיבוכיות תהיה $\displaystyle \Theta (n\log(n))$).

נניח שהמערך המקורי הוא $\displaystyle X$, והמערך הממויין הוא $\displaystyle X'$.

כל תת-מחרוזת עולה של $\displaystyle X$, נניח $\displaystyle Y$, היא תת-מחרוזת משותפת ל$\displaystyle X$ ו$\displaystyle X'$: היא בהכרח תת-מחרוזת של $\displaystyle X$ לפי ההגדרה, והיא תת-מחרוזת של $\displaystyle X'$ מפני שהיא מחרוזת עולה שאיבריה הם איברי $\displaystyle X$.

לכן, בפרט, תת-המחרוזת המשותפת הארוכה ביותר היא גם בהכרח תת-המחרוזת העולה הארוכה ביותר של $\displaystyle X$.