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 a_{1} < b_{1} < a_{2} < b_{2} < a_{3} < b_{3} . . . . where a_{1}, a_{2}, a_{3} . . . . is a subsequence of array A and b_{1}, b_{2}, b_{3} . . . . is a subsequence of array B.

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

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