Community

Ask A Question


Notifications
Subscribe You’re not receiving notifications from this thread.

Longest Increasing Subsequence (Main Thread)

Here is the interview question prompt, presented for reference.

The Longest Increasing Subsequence (LIS) is a subsequence within an array of numbers with an increasing order. The numbers within the subsequence have to be unique and in an ascending manner. It's important to note that the items of the sequence do not have to be in consecutive locations within the array.

Can you write an efficient program that finds the length of Longest Increasing Subsequence, also called LIS?

Examples

Here are some examples and their solutions:

``` Input: {1,5,2,7,3} LIS = 3. The longest increasing subsequence could be any of {1,5,7},{1,2,3},{1,2,7}

Input: {13,1,3,4,8,4} LIS = 4. The longest increasing subsequence {1,3,4,8}

Input: {13,1,3,4,8,19,17,8,0,20,14} LIS = 6. The longest increasing subsequence {1,3,4,8,17,20},{1,3,4,8,19,20} ```

Constraints

  • Length of the given array <= 100000
  • The array will always contain integer values between -2147483648 and 2147483647
  • Expected time complexity : O(nlogn)
  • Expected space complexity : O(n)

You can see the full challenge with visuals at this link.

Challenges • Asked about 3 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Nov 30, 2017:

This is the main discussion thread generated for Longest Increasing Subsequence.

bsanneh Commented on Jan 02, 2021:

Python is not supported too

Jake from AlgoDaily Commented on Jan 02, 2021:

Added to the queue for the team to address, will update when resolved. Keep these coming :-)

Jake from AlgoDaily Commented on Jan 03, 2021:

Updated and resolved :-)