Skip to content
Advertisement

Longest Increasing Subsequence using recursion and cache

i’ve been trying to implement a cache in my recursive LIS function so it doesn’t calculate the same value twice. I would really aprecciate if someone can give me a hint of what im getting wrong.

This is the recursive function that returns the LIS array that works fine:

JavaScript

This is the same function but implementing a cache, it gives wrong answers with repetition(in the case of the previous assert it returns [1, 20, 40, 40, 40, 40, 40]):

JavaScript

I think maybe the error is caching [l[i]] + lgsMemo(l[i],l,i+1) instead of lgsMemo(l[i],l,i+1).

Advertisement

Answer

Why make it so hard on yourself? You can just have two functions. One you call if you need to actually calculate things and one where you check if you have it in memory and delegate to the other if necessary. Notice that I had to slightly edit your recursive function so it uses the cache if possible.

JavaScript
User contributions licensed under: CC BY-SA
5 People found this is helpful
Advertisement