Estoy trabajando en https://leetcode.com/problems/longest-increasing-subsequence

Para caso de prueba

 input: [5, 4, 19, 5, 7, 12]; output: 4

Sin el caché, puedo generar 4 correctamente.

 var lengthOfLIS = function (ns) { if (ns.length === 1) return 1; const prev_i = -1; const curr_i = 0; const res = 0; return recur(ns, prev_i, curr_i, res); }; // good var recur = function (ns, prev_i, curr_i, res) { // if (curr_i >= ns.length) { return res; } // take let out_1 = 0; if (prev_i === -1) { out_1 = recur(ns, curr_i, curr_i + 1, res + 1); } else if (ns[curr_i] > ns[prev_i]) { out_1 = recur(ns, curr_i, curr_i + 1, res + 1); } else if (ns[curr_i] <= ns[prev_i]) { out_1 = res; } // !take let out_2 = 0; out_2 = recur(ns, prev_i, curr_i + 1, res); const max = Math.max(out_1, out_2); return max; };

Cuando le agrego caché, mi salida es 3.

 var recur = function (dp, ns, prev_i, curr_i, res) { // if (curr_i >= ns.length) { return res; } if (prev_i !== -1 && dp[prev_i + 1][curr_i + 1] !== undefined) { return dp[prev_i + 1][curr_i + 1]; } // take let out_1 = 0; if (prev_i === -1) { out_1 = recur(dp, ns, curr_i, curr_i + 1, res + 1); } else if (ns[curr_i] > ns[prev_i]) { out_1 = recur(dp, ns, curr_i, curr_i + 1, res + 1); } else if (ns[curr_i] <= ns[prev_i]) { out_1 = res; } // !take let out_2 = 0; out_2 = recur(dp, ns, prev_i, curr_i + 1, res); const max = Math.max(out_1, out_2); dp[prev_i + 1][curr_i + 1] = max; return max; }; var lengthOfLIS = function (ns) { if (ns.length === 1) return 1; const dp = Array(ns.length + 1) .fill(undefined) .map((_, i) => { return Array(ns.length + 1).fill(undefined); }); const prev_i = -1; const curr_i = 0; const res = 0; return recur(dp, ns, prev_i, curr_i, res); };

¿Alguien podría señalar algún error que cometí? Estoy tratando de usar el depurador para ver qué está sucediendo.