# LeetCode: Longest Increasing Subsequence Solution

Dynamic programming, top-down approach

## 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

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}/**2 * @param {number[]} nums3 * @return {number}4 */5var lengthOfLIS = function (nums) {6  const n = nums.length7  const memo = Array(n).fill(null)8
9  const recursion = i => {10    if (i === 0) {11      return 112    }13
14    if (memo[i] !== null) {15      return memo[i]16    }17
18    let res = 119
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 = 030
31  for (let i = 0; i < n; i++) {32    res = Math.max(res, recursion(i))33  }34
35  return res36}```

## Tags

leetcode

recursion

dynamic programming

## Next Post

LeetCode: Find Median from Data Stream

Jul 11, 2021

Insert and keep the array sorted

## Previous Post

LeetCode: Maximum Length of Repeated Subarray

Jul 8, 2021

Memoized recursion, somewhat similar to "Longest common subsequence"

Search Posts