What is Subsequence?

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence {A, B, D} is a subsequence of {A, B, C, D, E, F} obtained after removal of elements C, E, and F.

What is Longest Increasing Subsequence (LIS)?

The increasing subsequences of array {3, 2, 6, 4, 5, 1} are {3, 6}, {2, 6}, {2, 4, 5}, and {1}. The longest is {2, 4, 5}.

Problem

Find the longest subsequence in a given unsorted array of integers such that all elements of the subsequence are sorted in ascending order. For example, the longest increasing subsequence of {3, 2, 6, 4, 5, 1} is {2, 4, 5}.

Approach

Find the longest increasing subsequence of a given array


Time complexity: O(n2)
Space complexity: O(n)

Find only the length of the longest increasing subsequence of a given array


Time complexity: O(n2)
Space complexity: O(n)

References

Longest Increasing Subsequence (youtube.com)