You are given two arrays A (size m) and B (size n). You have to choose some elements from A and B such that the resulting array (size d) is lexicographically maximum. The only constraint here is that you have to maintain the relative ordering of the elements taken from the same array.
Example 1
Input
4 6 5
2 3 5 4
8 0 1 4 7 2
Output
8 7 5 4 2
Example 2
Input
2 3 5
7 8
7 1 5
Output
7 8 7 1 5
Constraints:
1 < m, n ≤ 512
1 < d ≤ (m + n)
0 ≤ A[i], B[j] ≤ 9
Go over every splitting case for 'd'. For example, try greedily taking 1 element from A and d — 1 element from B (if this is possible). Then merge the resultant arrays you obtained from A and B. Update the answer array. Constraints are small. This would probably work.