Day-20: Longest Increasing Subsequence

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

Author face

Abdurrezzak Efe

Bilkent University Bachelor's in CS 2018'

Recent post