LeetCode: Longest Increasing Subsequence Solution

Approach

recursion(i) returns the longest increasing subsequence of nums.slice(0, i)

• base case: 1 for i === 0 (only one element)
• max(1 + recursion(j)) for every j < i and nums[j] < nums[i]

Final result will be max(recursion(i)) all over i

Implementation

1/**
2 * @param {number[]} nums
3 * @return {number}
4 */
5var lengthOfLIS = function (nums) {
6  const n = nums.length
7  const memo = Array(n).fill(null)
8
9  const recursion = i => {
10    if (i === 0) {
11      return 1
12    }
13
14    if (memo[i] !== null) {
15      return memo[i]
16    }
17
18    let res = 1
19
20    for (let j = 0; j < i; j++) {
21      if (nums[j] < nums[i]) {
22        res = Math.max(res, 1 + recursion(j))
23      }
24    }
25
26    return (memo[i] = res)
27  }
28
29  let res = 0
30
31  for (let i = 0; i < n; i++) {
32    res = Math.max(res, recursion(i))
33  }
34
35  return res
36}