We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The video method is O(n^2). It can be done in O(nlog(n)). First, don't store the subsquences found but add a link to the previous subsequence in the step "previous subsequence + element". Second, you don't have to go trough all previous subsequences, you can keep only those with smallest last element (for each length) and use a bisection lookup (O(log(n)) instead O(n) search). See http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
The Longest Increasing Subsequence
You are viewing a single comment's thread. Return to all comments →
The video method is O(n^2). It can be done in O(nlog(n)). First, don't store the subsquences found but add a link to the previous subsequence in the step "previous subsequence + element". Second, you don't have to go trough all previous subsequences, you can keep only those with smallest last element (for each length) and use a bisection lookup (O(log(n)) instead O(n) search). See http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms