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.
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