LeetCode: Russian Doll Envelopes Solution

Approach

Longest increasing subsequence

Implementation

1/**
2 * @param {number[][]} envelopes
3 * @return {number}
4 */
5var maxEnvelopes = function (envelopes) {
6 const N = envelopes.length
7 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 = 1
16 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 = -Infinity
29 for (let i = 0; i < N; i++) {
30 max = Math.max(max, lis(i))
31 }
32
33 return max
34}

Comments

Loading comments...