# C++ 136ms solution

• ``````class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {

vector<int> res;
bool first = true;
for (int i=0; i<=k; i++) {

if (i > nums1.size() || k-i > nums2.size())
continue;

// Find max number from nums1 of length i
vector<int> maxNum1 = findMax(nums1, i);

// Find max number from nums2 of length k-i
vector<int> maxNum2 = findMax(nums2, k-i);

// Interleave to find the global max number
vector<int> candidate = interleave(maxNum1, maxNum2);

if (first) {
res = candidate;
first = false;
}
else if (compare(res, 0, candidate, 0))
res = candidate;
}
return res;
}
vector<int> findMax(vector<int>& nums, int len) {
vector<int> maxNum;
int prev_pos = -1;
int maxi;
for (int i=0; i<len; i++) {
maxi = -1;
int limit = nums.size()-len+i;
for (int j=prev_pos+1; j<=limit; j++) {
if (nums[j] > maxi) {
maxi = nums[j];
prev_pos = j;
}
}
maxNum.push_back(maxi);
}
return maxNum;
}
vector<int> interleave(vector<int>& maxNum1, vector<int>& maxNum2) {
vector<int> res;
int i1=0, i2=0;
while (i1<maxNum1.size() || i2<maxNum2.size()) {
if (compare(maxNum1, i1, maxNum2, i2)) {
res.push_back(maxNum2[i2++]);
}
else {
res.push_back(maxNum1[i1++]);
}
}
return res;
}
// Returns true if the new vec (starting at position j) is better than the old vec (starting at position i)
bool compare(vector<int>& old_vec, int i, vector<int>& new_vec, int j) {

while (i < old_vec.size() && j < new_vec.size() && old_vec[i]==new_vec[j]) {
i++;
j++;
}
return i==old_vec.size() || (j!=new_vec.size() && old_vec[i] < new_vec[j]);
}
};``````

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