# 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: 1fori === 0(only one element)
- max(1 + recursion(j))for everyj < iandnums[j] < nums[i]

Final result will be

max(recursion(i))

all over i

## Implementation

1/**2 * @param {number[]} nums3 * @return {number}4 */5var lengthOfLIS = function (nums) {6 const n = nums.length7 const memo = Array(n).fill(null)89 const recursion = i => {10 if (i === 0) {11 return 112 }1314 if (memo[i] !== null) {15 return memo[i]16 }1718 let res = 11920 for (let j = 0; j < i; j++) {21 if (nums[j] < nums[i]) {22 res = Math.max(res, 1 + recursion(j))23 }24 }2526 return (memo[i] = res)27 }2829 let res = 03031 for (let i = 0; i < n; i++) {32 res = Math.max(res, recursion(i))33 }3435 return res36}

## Comments

Loading comments...

## Tags

leetcode

recursion

dynamic programming

## Apply and earn a $2,500 bonus once you're hired on your first job!

Clients from the Fortune 500 to Silicon Valley startups

Choose your own rate, get paid on time

From hourly, part-time, to full-time positions

Flexible remote working environment

A lot of open JavaScript jobs!!

**Fact corner:** Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.

**Still hesitate?** Read HoningJS author's guide on dealing with Toptal interview process.

## Next Post

## Previous Post

LeetCode: Maximum Length of Repeated Subarray

Jul 8, 2021

Memoized recursion, somewhat similar to "Longest common subsequence"