LeetCode: Longest Increasing Subsequence Solution

Approach

returns the longest increasing subsequence of

• 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

all over

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}