# Share My 104ms C++ Solution

• 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;
}
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.