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


Input: arr[] = {5,4,1,2,3}  Output: Length of LIS = 3 Explanation: The longest increasing subsequence is 1,2,3.

1. Simple Approach  2. Dynamic Programming  3. Approach Greedy With Binary Search: Efficient Approach

Different Approaches 

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

Time complexity: O(2^N), where N is array size Space complexity: O(N) for stack space in recursion.

Explore other approaches and learn how to implement them in different languages.