Longest Increasing Subsequence
Explore the longest increasing subsequence problem and understand how to solve it with dynamic programming. Learn to optimize from exponential to polynomial time by applying recurrence relations and memoization. This lesson covers both the theory and implementation details needed to compute and print the longest increasing subsequence in a given sequence.
We'll cover the following...
Problem statement
The Longest Increasing Subsequence (LIS) problem requires you to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for {10, 9, 3, 5, 4, 11, 7, 8} is 4 and LIS is {3, 4, 7, 8}.
Solution: Naïve approach
The simplest approach is to try to find all increasing subsequences and then returning the maximum length of the longest increasing subsequence.
- Time complexity : O(