Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n2) complexity.
• Follow up: Could you improve it to O(n log n) time complexity?

Used in

• russian doll

Pseudo Code

• L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or
• L(i) = 1, if no such j exists.
• return max(L(i)) where 0 < i < n.

Solution

// Brute Force 
function lis(nums) {
  function helper(nums, prev = 0, cur = 0) {
    let taken = 0
    if (cur === nums.length) return 0

    if (nums[cur] > prev)
      taken = helper(nums, nums[cur], cur + 1) + 1
    let nottaken = helper(nums, prev, cur + 1)
    return Math.max(taken, nottaken)
  }
  return helper(nums)
};

// alternate implementation
function lis(arr, n){
  let maxRef = 1
  function helper(arr, n){
    if (n==1) return 1

    let res, maxEndingHere = 1

    for (let i=1;i<n;i++) {
      res = helper(arr, i)
      if (arr[i-1] < arr[n-1] && res+1 > maxEndingHere)
        maxEndingHere = res+1
    }

    if (maxRef < maxEndingHere) maxRef = maxEndingHere
    return maxEndingHere

  }
  helper(arr, n)
  return maxRef

}

let arr = [10, 22, 9, 33, 21, 50, 41, 60]
let n = arr.length
lis(arr, n)

// dp
var lengthOfLIS = function(sequence) {
  // Create array with longest increasing substrings length and
  // fill it with 1-s that would mean that each element of the sequence
  // is itself a minimum increasing subsequence.
  const lengthsArray = Array(sequence.length).fill(1);

  let previousElementIndex = 0;
  let currentElementIndex = 1;

  while (currentElementIndex < sequence.length) {
    if (sequence[previousElementIndex] < sequence[currentElementIndex]) {
      // If current element is bigger then the previous one then
      // current element is a part of increasing subsequence which
      // length is by one bigger then the length of increasing subsequence
      // for previous element.
      const newLength = lengthsArray[previousElementIndex] + 1;
      if (newLength > lengthsArray[currentElementIndex]) {
        // Increase only if previous element would give us bigger subsequence length
        // then we already have for current element.
        lengthsArray[currentElementIndex] = newLength;
      }
    }

    // Move previous element index right.
    previousElementIndex += 1;

    // If previous element index equals to current element index then
    // shift current element right and reset previous element index to zero.
    if (previousElementIndex === currentElementIndex) {
      currentElementIndex += 1;
      previousElementIndex = 0;
    }
  }

  // Find the biggest element in lengthsArray.
  // This number is the biggest length of increasing subsequence.
  let longestIncreasingLength = 0;

  for (let i = 0; i < lengthsArray.length; i += 1) {
    if (lengthsArray[i] > longestIncreasingLength) {
      longestIncreasingLength = lengthsArray[i];
    }
  }

  return longestIncreasingLength;
};