Longest Increasing Subsequence
How to find it?
Given a string, find the length of longest subsequence of a given sequence that has all elements sorted in increasing order.
Problem Statement
Learn More
Example-
Input:
arr[] = {5,4,1,2,3}
Output:
Length of LIS = 3
Explanation:
The longest increasing subsequence is 1,2,3.
Check other examples
1. Simple Approach
2. Dynamic Programming
3. Approach Greedy With Binary Search: Efficient Approach
Different Approaches
Learn More
Since a subsequence can start anywhere, we will apply a simple approach that fixes every index to calculate subsequent at each ending index. From this, we can find a recurrence relation.
Simple Approach
Check code explanation
Time complexity:
O(2^N), where N is array size
Space complexity:
O(N) for stack space in recursion.
Learn More
Explore other approaches and learn how to implement them in different languages.
Find Out Now