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