Suppose I have two digit arrays, A and B as follows
A = [3,4,5,6]
B = [9,8,3]
Now, I have to interleave the two arrays which would mean to pop the first element from both the arrays, at any given point of time. One such interleaving would be as follows,
Choose 3 from A
A = [4,5,6]
B = [9,8,3]
Choose 9 from B
A = [4,5,6]
B = [8,3]
Choose 4 from A
A = [5,6]
B = [8,3]
Choose 8 from B
A = [5,6]
B = [3]
Choose 5 from A
A = [6]
B = [3]
Choose 3 from B
A = [6]
B = []
Choose 6 from A
A = []
B = []
Output array = [3,9,4,8,5,3,6]
In other words, one can choose elements from both A and B but will have to be chosen sequentially.
Now, the question is how can one produce the array that is maximal. In this case, the maximal number would be [9,8,3,4,5,6,3].
P.S. I have already come up about how to solve this with dynamic programming, with the time complexity of $O(mn)$(Here $n$ and $m$ are the lengths of the arrays A and B respectively. But I am actually looking for something more effective(maybe linear time?). The tricky situation is when choosing elements that are equal, and that is where one can optimize. Here I have assumed digits, but each of the arrays could be a separate string as well.
