Day-20: Longest Increasing Subsequence

LIS is a commonly asked interview problem.

The naive approach would find the sequence by trying every possible subsequence which takes a lot of time.

A better approach is surely Dynamic Programming.

The DP solution takes the array, copies it, sorts the copied version and finds the longest common subsequence of both arrays which happens to be the answer we are looking for!

Time complexity: O(n^2)

Here is the link of my C++ implementation of LIS: LIS