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

עליך למצוא אלגוריתם יעיל למציאת הLIS לכל סידרה $\displaystyle X$:

1. אנא תאר אלגוריתם יעיל המוצא את אורך הLIS.

1. אנא תאר אלגוריתם יעיל המדפיס את הLIS עצמו.

שימו לב: בכל אחד משני הסעיפים: הנח שX הוא מערך גלובלי המתאר את הסדרה $\displaystyle X$, בעלת האורך $\displaystyle n$. אנא הוכח נכונות תשובתך, ומצא פתרון שסיבוכיותו $\displaystyle O(n^{2})$.