Special sequence

The question has been asked in one of the hackerearth hiring challenges (closed now). The problem statement is given below -

You have given the following:

  • An array A of length N
  • An array B of length M.

A special sequence is such that a1 < b1 < a2 < b2 < a3 < b3 . . . . where a1, a2, a3 . . . . is a subsequence of array A and b1, b2, b3 . . . . is a subsequence of array B.

Print the maximum length of the special sequence that can be obtained.

Sample Input 1 –

A = 4 2 10 5 9
B = 4 5 6 15

Output –
6

special sequence – 2, 4, 5, 6, 9, 15

Let L(i,j) be the longest special sequence (SS) considered till elements a[i] and b[j].

Case 0: L(0,0)=0 , L(i,0)=1 and L(0,j)=0

Case 1: If a[i]=b[j], we can’t include them in the sequence. So, L(i,j)=max(L(i-1,j),L(i,j-1))

Case 2: If a[i]<b[j], we have to find the longest SS with b[k] as its end element (k<j) and b[k]<a[i]. So, L(i,j)=1+max(L(i,k)) such that 1<=k<j and b[k]<a[i]

Case 3: If b[j]<a[i], we have to find the longest SS with a[k] as its end element (k<i) and a[k]<b[j]. So, L(i,j)=1+max(L(k,j)) such that 1<=k<i and a[k]<b[j]

This is my idea and I know it isn’t optimized. So, anyone is welcome to help me with an optimization :slight_smile:

1 Like