```
class list1
{
vector<int> a;
vector<vector<int>> f;
public:
list1() = delete;
inline int size() {return a.size();}
inline int next(int x,int d) {return f[x][d];}
list1(vector<int>& a0)
{
a = a0;
f = vector<vector<int>>(a0.size() + 1,vector<int>(10,INT_MAX));
for (int i = 0;i<a0.size();i++)
{
f[i][a[i]] = i;
for (int j = i-1;j>=0;j--)
{
if (a[j] == a[i]) break;
f[j][a[i]] = i;
}
}
}
};
//dmd for detect_max_digit
// dmd(a,x,rem) -> (max_digit, pos) , where a[pos-1] == max_digit
// list a , from x, need rem numbers, x not included.
pair<int,int> dmd(list1& a,int x,int rem)
{
for (int d = 9;d >= 0;d--)
{
int pos = a.next(x,d);
if (pos == INT_MAX) continue;
if (a.size() - (pos + 1) >= rem)
return make_pair(d,pos + 1);
}
}
class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
list1 a1 = list1(nums1);
int N1 = nums1.size();
list1 a2 = list1(nums2);
int N2 = nums2.size();
auto ret = vector<int>(k,0);
auto f = vector<int>(N1 + 1,0);
//f[i] denote a1[0..i-1] need a2[0..f[i]-1] to reach the current maximal number, and can expand to length k
// in other words, the state is : the number is current maximal and can be expanded, list1 begin with a1[i] and list2 with a2[f[i]]
for (int d = 1;d <= k;d++)
{
int maxDigit = -1;
auto tmpf = vector<int>(N1 + 1,INT_MAX);
for (int x = 0;x<=N1;x++)
{
int y = f[x];
if (y == INT_MAX) continue;
auto m1 = dmd(a1,x,k-d-(N2-y));
auto m2 = dmd(a2,y,k-d-(N1-x));
maxDigit = max(maxDigit,m1.first);
maxDigit = max(maxDigit,m2.first);
}
ret[d-1] = maxDigit;
for (int x = 0;x<=N1;x++)
{
int y = f[x];
if (y == INT_MAX) continue;
auto m1 = dmd(a1,x,k-d-(N2-y));
if (m1.first == maxDigit)
tmpf[m1.second] = min(tmpf[m1.second],y);
auto m2 = dmd(a2,y,k-d-(N1-x));
if (m2.first == maxDigit)
tmpf[x] = min(tmpf[x],m2.second);
}
f = tmpf;
}
return ret;
}
};
```

Any Question is welcome and will be answered as soon as possible.

Detailed explanation is coming soon!

You may firstly read my code, it's quite easy to understand.

## Detailed Solution

Let a1,a2 be the two list from where we construct the maximal number.

Let N1,N2 denote the size of a1,a2.

We construct the maximal number digit by digit.

Suppose we are constructing the d-th digit(ret[0..d-1] is done) and we have a set of states S = {(a1,b1),(a2,b2),...(a_N,b_N)},For each state (x,y) in S, it means we use a1[0..(x-1)] and a2[0..(y-1)] to construct ret[0..d-1] and a1[x..N1] and a2[y..N2] are avaliabe to construct the remaining digits.

In the iteration, we need to construct the d-th digit as well as the set S', that is from where we can construct the d+1-th digit.

For every state (x,y) in S, we use the function "dmd" to obtain the biggest d-th digit we can get from it.

Let maxdigit = {max(dmd(x,y)[1])|(x,y) in S}, it is the d-th digit.

As we now the d-th digit,

We scan S again,

For every state (x,y) in S, we use the function "dmd" to obtain the (x',y) and (x,y') it extands to,

if a1[x'-1] == maxdigit, we add (x',y) to S'.

if a2[y'-1] == maxdigit, we add (x,y') to S'.

Now we can construct the d+1-th digit from S', note that the size of S' is at most N1, for(x,y1) and (x,y2), y1 < y2, (x,y2) is needless to be recorded.

Finally I'd like to use an typical example to illustrate the process.

a1 = [8,1] a2 = [8,9] k = 4

S = {(0,0)}

the first digit is 8,

S' = {(0,1),(1,0)}

the second digit is 9, we construct it from (0,1)

S'' = {(0,2)}

the remain digits are 8 and 1,

we finally reach 8981.