Given two arrays, a[] and b[], find the length of the longest common increasing subsequence(LCIS). LCIS refers to a subsequence that is present in both arrays and strictly increases.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Longest common increasing subsequence (LCS + 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:

# Python implementation

cache = None

def count(a, b, last):
  if len(a) <= 0 or len(b) <= 0:
    return 0

  global cache
  if not cache:
    cache = [[{} for _ in range(len(b) + 1)] for _ in range(len(a) + 1)]
  
  if last not in cache[len(a)][len(b)]:
    result = 0

    if a[0] == b[0]:
      if last < a[0]:
        result = 1 + count(a[1:], b[1:], a[0])

    cache[len(a)][len(b)][last] = max(result, count(a[1:], b, last), count(a, b[1:], last))
  
  return cache[len(a)][len(b)][last]

a = [3, 4, 9, 1]
b = [5, 3, 8, 9, 10, 2, 1]

print(count(a, b, -1))

// Javascript implementation

let cache = null;

function count(a, b, last) {
  if (a.length <= 0 || b.length <= 0) {
    return 0;
  }

  if (cache === null) {
    cache = [];
    
    for (let i = 0; i < a.length + 1; i++) {
      cache[i] = [];

      for (let j = 0; j < b.length + 1; j++) {
        cache[i][j] = {}
      }
    }
  }

  if (cache[a.length][b.length][last] === undefined) {
    let result = 0;

    if (a[0] === b[0]) {
      if (last < a[0]) {
        result = 1 + count(a.slice(1), b.slice(1), a[0]);
      }
    }
  
    cache[a.length][b.length][last] = Math.max(result, count(a.slice(1), b, last), count(a, b.slice(1), last));
  }

  return cache[a.length][b.length][last];
}

const a = [3, 4, 9, 1];
const b = [5, 3, 8, 9, 10, 2, 1];

console.log(count(a, b, -1));

Longest common increasing subsequence (LCS + LIS) (Memoization)

Hint