# 40ms clean C++ solution

• ``````class Solution {
public:

vector<vector<int>> dp(const vector<int>& nums)
{
int len = nums.size();
vector< vector<int> > mem(len+1);
mem[len] = nums;
for (int i=len-1; i >=0; i--)
{
mem[i] = mem[i+1];
for (int j=1; j <  mem[i].size(); j++)
{
if ( mem[i][j] > mem[i][j-1])
{
mem[i].erase( mem[i].begin() + j-1);
break;
}
}
mem[i].resize(i);
}

return mem;
}

vector<int> special_merge(const vector<int>& res1,const vector<int>& res2, int k)
{
vector<int> res(k);
int idx1=0, idx2=0, idx=0;

// take the largest number. In case of equality take from the sequence that leads faster to a larger number.
while ( idx1 < res1.size() && idx2 < res2.size())
{
if (res1[idx1] > res2[idx2])
{
res[idx++] =  res1[idx1++];
}
else if (res1[idx1] < res2[idx2])
{
res[idx++] = res2[idx2++];
}
else
{
int tmp = res1[idx1];
auto r = lexicographical_compare( res1.begin() + idx1, res1.end(), res2.begin() + idx2, res2.end() )
? make_pair( ref(res2), ref(idx2)) : make_pair( ref(res1), ref(idx1));

while ( r.second < r.first.size() && r.first[r.second] == tmp)
{
res[idx++] =  r.first[r.second++];
}
}
}
auto it = copy(res1.begin()+idx1, res1.end(), res.begin() + idx );
copy( res2.begin()+idx2, res2.end(), it );
return res;
}

vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k)
{
// find best sub-sequences of nums1 and nums2 for all possible lengths
auto mem1 = dp(nums1);
auto mem2 = dp(nums2);

int M = min( k ,  (int) nums1.size());  // Maximum items we can take from nums1
int m = std::max(0, k - (int) nums2.size() ); // Minimum items we can take from nums1

vector<int> result;
for (int n1 =m; n1 <= M; n1++)
{
result = max( result,  special_merge( mem1[ n1], mem2[k-n1], k) );
}

return result;
}
};``````

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