Find longest increasing subsequence (LIS) (Memoization)

Given an array of size n, find the length of the longest increasing subsequence (LIS), in which the elements of the subsequence are sorted in increasing order.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Find longest increasing subsequence (LIS), but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

• Initialize cache to store results.
• Using the key to check cached result. If the result is not found in the cache, do the calculation and save the result in cache.
• Return the cached result.

• Python
• Javascript
•  Run

cache = {}

def count(ls):
  last = len(ls) - 1

  if last == 0:
    return 1
  
  global cache
  if last not in cache:
    mx = 1
    
    for i in range(last):
      if ls[i] < ls[last]:
        mx = max(mx, 1 + count(ls[0:i + 1]))

    cache[last] = mx

  return cache[last]

ls = [3, 10, 2, 1, 20]

mx = 1

for i in range(len(ls)):
  mx = max(mx, count(ls[0:i + 1]))

print(mx)

const cache = []

function count(list) {
  const last = list.length - 1;

  if (last == 0) {
    return 1;
  }
  
  if (cache[last] === undefined) {
    let max = 1;
    
    for (let i = 0; i < last; i++) {
      if (list[i] < list[last]) {
        max = Math.max(max, 1 + count(list.slice(0, i + 1)));
      }
    }

    cache[last] = max;
  }

  return cache[last];
}

const list = [3, 10, 2, 1, 20];

let max = 1;

for (let i = 0; i < list.length; i++) {
  max = Math.max(max, count(list.slice(0, i + 1)));
}

console.log(max);