مسئلهٔ طولانی ترین زیر رشته صعودی (به انگلیسی: Longest increasing subsequence) یا LIS این است که در یک رشتهٔ داده شده طولانی ترین زیر رشته ای را بیابیم که عناصر آن زیر رشته از کوچک به بزرگ مرتب شده باشند. اعضای زیر رشتهٔ انتخاب شده لزومی ندارد متوالی باشد.
Aldous D.J. and Diaconis, P. (1999). Longest Increasing Subsequences: From
مسئلهٔ طولانی ترین زیر رشتهٔ صعودی در زمان (O(n log n قابل حل است البته الگوریتم های ساده تری با زمان n 2 {\displaystyle n^{2}} نیز دارد. با فرض این که n طول رشتهٔ اصلی باشد که می خواهیم در ان مسئله را حل کنیم.
برای مثال به رشته زیر توجه کنید.
یک طولانی ترین زیر رشتهٔ صعودی از رشتهٔ داده شده برابر رشتهٔ زیر است.
Aldous D.J. and Diaconis, P. (1999). Longest Increasing Subsequences: From
مسئلهٔ طولانی ترین زیر رشتهٔ صعودی در زمان (O(n log n قابل حل است البته الگوریتم های ساده تری با زمان n 2 {\displaystyle n^{2}} نیز دارد. با فرض این که n طول رشتهٔ اصلی باشد که می خواهیم در ان مسئله را حل کنیم.
برای مثال به رشته زیر توجه کنید.
یک طولانی ترین زیر رشتهٔ صعودی از رشتهٔ داده شده برابر رشتهٔ زیر است.