Longest common increasing subsequence (LCS + LIS)

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 identifies the Longest Common Subsequence (LCS) within two given arrays. It operates by comparing elements between the arrays. Begin by examining the first elements of both arrays. At each comparison, three possible actions arise:

Match and Increase: If the current elements in both arrays match and the current element is greater than the previous element in the LCS, include this element in the LCS and proceed to compare the next elements in both arrays.
Skip in Array 1: If the match condition is not met, consider the possibility of finding a match by moving to the next element in the first array while keeping the current position in the second array.
Skip in Array 2: Alternatively, explore the possibility of a match by moving to the next element in the second array while maintaining the current position in the first array.

Evaluates these choices, selects path that results in the longest common subsequence. To ensure the subsequence is strictly increasing, the algorithm maintains a "last" variable. This variable stores the last element included in the LCS, preventing the inclusion of any smaller elements that would violate the increasing order.

Python
Javascript

# Python implementation

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

  result = 0

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

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

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

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

// Javascript implementation

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

  let result = 0;

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

  return Math.max(result, count(a.slice(1), b, last), count(a, b.slice(1), last));
}

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

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