How can I add proper memoization to optimize this recursive algorithm

Question

I am looking at this leetcode question where I write a function that takes an array of numbers and output the biggest sum of non-contiguous sub-arrays.

For example, if the array is [1,2,3,1], the output is 4 because 1 + 3 if the array is [2,7,9,3,1] the output is 12 because 2 + 9 + 1 = 12

Here is my attempt:


var rob = function (nums) {
  const recurse = (index, path) => {
    if (index >= nums.length) return path.reduce((sum, i) => sum + nums[i], 0)

    let rob = -Infinity
    if (index !== path.at(-1) + 1) {
      rob = recurse(index + 1, path.concat(index))
    }

    const notRob = recurse(index + 1, path)

    return Math.max(rob, notRob)
  }

  return recurse(0, [])
}

rob([1,2,3,1]) // 4
rob([2,7,9,3,1]) // 12

This function works but it times out on Leetcode as it didn't have memorization to optimize repeated calculations. So I added one where the cache key is the index:

var rob = function (nums) {
  const memo = new Map()

  const recurse = (index, path) => {
    if (index >= nums.length) return path.reduce((sum, i) => sum + nums[i], 0)
    if (memo.has(index)) {
      return memo.get(index)
    }

    let rob = -Infinity
    if (index !== path.at(-1) + 1) {
      rob = recurse(index + 1, path.concat(index))
    }

    const notRob = recurse(index + 1, path)
    const max = Math.max(rob, notRob)
    memo.set(index, Math.max(rob, notRob))

    return max
  }

  return recurse(0, [])
}

Now this solution is no longer correct. For example, with rob([1, 3, 1]) it outputs 2 instead of 3.

I can't wrap my head around why this memorization is incorrect. If I tweaked my implementation slightly, this very same memorization ends up working just fine:


var rob2 = function (nums) {
  const memo = new Map()
  const recur = (index) => {
    if (index >= nums.length) return 0
    if (memo.has(index)) return memo.get(index)
    const rob = nums[index] + recur(index + 2)
    const notRob = recur(index + 1)
    const max = Math.max(rob, notRob)
    memo.set(index, max)
    return max
  }

  return recur(0)
}

Can someone explain to me why this happened? Also what is the time complexity if we don't add the memorization?

Maybe because in [1, 3, 1] only firs and last 1 is non-contiguous? — tarkh
– tarkh, Commented Sep 11, 2022 at 20:20

Alois Christen · Accepted Answer · 2022-09-13 07:10:52Z

2

[Edit for clarification]

The cache key was right, it's the value stored that was wrong : for each cache, you stored the value of the first solution you tried for the whole array. Let's take a look at what happened :

You call recurse(0, [])
recurse(0, []) - You check map[0], there is no value
recurse(0, []) - You call recurse(1,[0]) to compute RoB
recurse(1, [0]) - You check map[1], there is no value
recurse(1, [0]) - You set RoB at -inf
recurse(1, [0]) - You call recurse(2, [0]) to compute notRoB
recurse(2, [0]) - You check map[2], there is no value
recurse(3, [0,2]) -You call recurse(3,[0,2]) to compute RoB
recurse(3, [0,2]) -index > nums.length -> you return the sum (0 + 2 -> 2)
recurse(2, [0]) - You call recurse(3, [0]), to compute notRoB
recurse(3, [0]) -index > nums.length -> you return the sum (0 -> 0)
recurse(2, [0]) - You take the max of RoB and notRoB (0,2 -> 2)
recurse(2, [0]) - You store the max in the cache and return it (map[2] = 2)
recurse(1, [0]) - You take the max of RoB and notRob (-inf, 2 -> 2)
recurse(1, [0]) - You store the max in the cache, and return it (map[1] = 2)
recurse(0, []) - You call recurse(1,[]) to compute notRoB
recurse(1, []) - You check map[1], you find 2 and return it
recurse(0, []) - You take the max of RoB and notRoB (2,2 -> 2)
recurse(0, []) - You store the max in cache and return it (map[0] = 2)
The solution found is 2.

The problem is that you compute the solution from start to finish (by using path), but store them from finish to start (first your store map[2], then map[1], etc.) but you use path for the value. That means that the stored value is set to the first solution you try, thus all solution will have the same value.

[End of edit]

There is 2 main problem with your first solution :

First, the memoization is wrong : the value you set is the total of the numbers taken before current index (path in your code). This should be best solution starting from current index (including index).
Second, when you call recurse(1, [0]), you set the map[1], even if you did not take the value at index 1. This means that anytime you'll look at this index in the future, you'll get the value of recurse(2, [0]), so you never compute recurse(1, []) properly.

Complexity without memoization is roughly O((1.6)^n) : if f(n) is the "number of actions" done for an array of n elements, then an array of n+1 will requier f(n-1) + f(n) actions. This is the fibonacci sequence, with a growth of (1.6)^n

edited Sep 13, 2022 at 7:10

answered Sep 11, 2022 at 20:56

Alois Christen

5454 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Joji Over a year ago

hey could you elaborate on what you think the right cache key should be? I am not sure if I understand what you meant there? did you mean that it should be index+ 1 instead of index?

Joji Over a year ago

can you elaborate what you meant by "best total of subarray after index (including index)." It'd be great if you can just modify the code

Alois Christen Over a year ago

I added clarification, changed "best total of subarray after index (including index)." to "best solution starting from current index (including index)." and made a step by step analysis of the first solution. I won't modify the code, as your second attempt is exactly what I would do.

Collectives™ on Stack Overflow

How can I add proper memoization to optimize this recursive algorithm

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related