1var assert = require('assert');
2
3/**
4 * Dynamic programming approach to find longest increasing subsequence.
5 * Complexity: O(n * n)
6 *
7 * @param {number[]} arr
8 * @return {number}
9 */
10
11function LISsolveDP(arr) {
12  // Create an array for longest increasing substrings lengths and
13  // fill it with 1s. This means that each element of the arr
14  // is itself a minimum increasing subsequence.
15  const lengthsArr = Array(arr.length).fill(1);
16
17  let prevElIdx = 0;
18  let currElIdx = 1;
19
20  while (currElIdx < arr.length) {
21    if (arr[prevElIdx] < arr[currElIdx]) {
22      // If current element is bigger then the previous one. then
23      // it is a part of increasing subsequence where length is
24      // by 1 bigger then the length of increasing subsequence
25      // for the previous element.
26      const newLen = lengthsArr[prevElIdx] + 1;
27      if (newLen > lengthsArr[currElIdx]) {
28        // Increase only if previous element would give us a
29        // bigger subsequence length then we already have for
30        // current element.
31        lengthsArr[currElIdx] = newLen;
32      }
33    }
34
35    // Move previous element index right.
36    prevElIdx += 1;
37
38    // If previous element index equals to current element index then
39    // shift current element right and reset previous element index to zero.
40    if (prevElIdx === currElIdx) {
41      currElIdx += 1;
42      prevElIdx = 0;
43    }
44  }
45
46  // Find the largest element in lengthsArr, as it
47  // will be the biggest length of increasing subsequence.
48  let longestIncreasingLength = 0;
49
50  for (let i = 0; i < lengthsArr.length; i += 1) {
51    if (lengthsArr[i] > longestIncreasingLength) {
52      longestIncreasingLength = lengthsArr[i];
53    }
54  }
55
56  return longestIncreasingLength;
57}
58
59try {
60  assert.equal(LISsolveDP([1, 5, 2, 7, 3]), 3);
61
62  console.log('PASSED: ' + '`LISsolveDP([1,5,2,7,3])` should return `3`');
63} catch (err) {
64  console.log(err);
65}
66
67try {
68  assert.equal(LISsolveDP([13, 1, 3, 4, 8, 4]), 4);
69
70  console.log('PASSED: ' + '`LISsolveDP([13,1,3,4,8,4])` should return `4`');
71} catch (err) {
72  console.log(err);
73}
74
75try {
76  assert.equal(LISsolveDP([13, 1, 3, 4, 8, 19, 17, 8, 0, 20, 14]), 6);
77
78  console.log(
79    'PASSED: ' + '`LISsolveDP([13,1,3,4,8,19,17,8,0,20,14])` should return `6`'
80  );
81} catch (err) {
82  console.log(err);
83}