AlgoDaily - Longest Increasing Subsequence

Longest Increasing Subsequence (Hard)

Good afternoon! Here's our prompt for today.

You may see this problem at Morgan Stanley, Segment, Lucid Software, Benchling, Zoom, Motorola, Cornerstone, and Smartsheet.

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:

SNIPPET

1Input: {1,5,2,7,3}
2LIS = 3.  The longest increasing subsequence could be any of {1,5,7},{1,2,3},{1,2,7}
3
4Input: {13,1,3,4,8,4}
5LIS = 4.  The longest increasing subsequence {1,3,4,8}
6
7Input: {13,1,3,4,8,19,17,8,0,20,14}
8LIS = 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 -1000000000 and 1000000000
Expected time complexity : O(nlogn)
Expected space complexity : O(n)

xxxxxxxxxx
​
 
var assert = require('assert');
​
/**
 * Dynamic programming approach to find longest increasing subsequence.
 * Complexity: O(n * n)
 *
 * @param {number[]} arr
 * @return {number}
 */
​
function LISsolveDP(arr) {
  // Create an array for longest increasing substrings lengths and
  // fill it with 1s. This means that each element of the arr
  // is itself a minimum increasing subsequence.
  const lengthsArr = Array(arr.length).fill(1);
​
  let prevElIdx = 0;
  let currElIdx = 1;
​
  while (currElIdx < arr.length) {
    if (arr[prevElIdx] < arr[currElIdx]) {
      // If current element is bigger then the previous one. then
      // it is a part of increasing subsequence where length is
      // by 1 bigger then the length of increasing subsequence
      // for the previous element.
      const newLen = lengthsArr[prevElIdx] + 1;
      if (newLen > lengthsArr[currElIdx]) {

OUTPUT

Results will appear here.