Longest Increasing Subsequence: Compute and Implement Efficient Solution
Learn how to compute the longest increasing subsequence (LIS) efficiently using dynamic programming. Understand the recursive and dynamic programming approaches, and implement the solution step by step. Visual aids and explanations provided for better understanding.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Dynamic Programming (4) Longest Increasing Subsequence (LCS)
The input Sequence ? = ?1,?2,?3, ,??of integers Example: 2, 4, 3, 5, 1, 7, 6, 9, 8
Increasing subsequence Increasing subsequence: 2, 4, 3, 5, 1, 7, 6, 9, 8
Compute Longest Increasing subsequence
Compute Longest Increasing subsequence: 2, 4, 3, 5, 1, 7, 6, 9, 8
Compute Longest Increasing subsequence: 2, 4, 3, 5, 1, 7, 6, 9, 8
Compute Longest Increasing subsequence: 2, 4, 3, 5, 1, 7, 6, 9, 8 1. We want the length ? of this sequence 2. Then we want indices ?1 ?2 ?? such that ??1 ??2 ???
Recursive solution ? Suppose we computed the length of the LIS of ?1,?2,s3, ,?? 1 Can we deduce the length of the LIS of ?1,?2,s3, ,?? ?
Recursive solution ? Well, we really want to know what is the smallest integer that can end an LIS.. But if we expect to get this from the recursive call then we also have to compute this Suppose we know the smallest integer in an LIS of ?1,?2,s3, ,?? 1, Can we compute the smallest integer in an LIS of ?1,?2,s3, ,?? 1,?? ? We will come back to this reasoning
Dynamic programming The pattern we have seen is that the subproblems are of the same kind as the problem we want to solve but on a shorter/smaller instance Each subproblem is solved based on a constant number of smaller subproblems ( 2 in our previous examples..) This need not necessarily be the case
Dynamic programming The idea is to compute for each 1 ? ?: L[i] = The length of the longest increasing subsequence ending with ?? ? 1 2 3 4 5 6 7 8 9 ? 2 4 3 5 1 7 6 9 8 L
Dynamic programming The idea is to compute for each 1 ? ? L[i] = The length of the longest increasing subsequence ending with ?? ? 1 2 3 4 5 6 7 8 9 ? 2 4 3 5 1 7 6 9 8 L 1 2 2 3 1 4 4 5 5 ? ? = max ? ? ??< ?? + 1 ?<?
Finding the sequence itself The idea is to compute for each 1 ? ? L[i] = The length of the longest increasing subsequence ending with ?? ? 1 2 3 4 5 6 7 8 9 ? 2 4 3 5 1 7 6 9 8 L 1 2 2 3 1 4 4 5 5 P P[i] = The index of the element that precedes ?? in the longest sequence that ends at ??
Dynamic programming The idea is to compute for each 1 ? ? L[i] = The length of the longest increasing subsequence ending with ?? ? 1 2 3 4 5 6 7 8 9 ? 2 4 3 5 1 7 6 9 8 L 1 2 2 3 1 4 4 5 5 P 1 1 2 4 4 6 6 P[i] = The index of the element that precedes ?? in the longest sequence that ends at ??
