# LeetCode: Russian Doll Envelopes Solution

## Approach

Longest increasing subsequence

## 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[][]} envelopes3 * @return {number}4 */5var maxEnvelopes = function (envelopes) {6  const N = envelopes.length7  const mem = Array(N).fill(null)8  envelopes.sort((a, b) => a[0] - b[0])9
10  const lis = i => {11    if (mem[i] !== null) {12      return mem[i]13    }14
15    let res = 116    for (let j = 0; j < i; j++) {17      if (18        envelopes[j][0] < envelopes[i][0] &&19        envelopes[j][1] < envelopes[i][1]20      ) {21        res = Math.max(res, 1 + lis(j))22      }23    }24
25    return (mem[i] = res)26  }27
28  let max = -Infinity29  for (let i = 0; i < N; i++) {30    max = Math.max(max, lis(i))31  }32
33  return max34}```

## Tags

leetcode

dynamic programming

## Next Post

LeetCode: Swapping Nodes In A Linked List

Mar 31, 2021

Search Posts