One Pager Cheat Sheet

• An efficient program that can find the length of the Longest Increasing Subsequence (LIS) should satisfy the constraints of O(nlogn) time complexity and O(n) space complexity.
• We can use a recursive algorithm to compute the length of the LIS for an array, which is the maximum of LIS(arr, n) for all the valid indices n of the array.
• A pseudo-code is written to compute the Length of Longest Increasing Subsequence in an array using recursive cases and base cases, which helps to reduce the time complexity to O(2^n).
• Dynamic Programming can be used to break down a problem into smaller repeating sub-problems and significantly reduce the time complexity from O(n^2) to O(n) by storing the solutions of the sub-problems and using them later when needed.
• Implementing Longest Increasing Subsequence (LIS) using Dynamic Programming may be accomplished by following the steps outlined and working through examples on paper, before coding it in any language.
• LISArray stores the indices of the items of the input array in sorted order, allowing for the comparison of elements at specified indices in the original array.
• Armed with this knowledge, we are now ready to construct an O(n log n) algorithm for solving LIS efficiently.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

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]) {

        // Increase only if previous element would give us a

        // bigger subsequence length then we already have for

        // current element.

        lengthsArr[currElIdx] = newLen;

      }

Alright, well done! Try another walk-through.

If you had any problems with this tutorial, check out the main forum thread here.