You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers. You are also given an integer k.

Create the maximum number of length k &lt;= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved.

Return an array of the k digits representing the answer.

&nbsp;
Example 1:

Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
Output: [9,8,6,5,3]


Example 2:

Input: nums1 = [6,7], nums2 = [6,0,4], k = 5
Output: [6,7,6,0,4]


Example 3:

Input: nums1 = [3,9], nums2 = [8,9], k = 3
Output: [9,8,9]


&nbsp;
Constraints:


	m == nums1.length
	n == nums2.length
	1 &lt;= m, n &lt;= 500
	0 &lt;= nums1[i], nums2[i] &lt;= 9
	1 &lt;= k &lt;= m + n


class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        m = len(nums1)
        n = len(nums2)
        dp = {}
        
        # get the max number string with "length" from index "i" in nums1 and index "j" in nums2
        # using number string to easy to compare
        def getMaxNumberString(i, j, length):
            if length == 0:
                return ""
            
            # using memoization to optimize for the overlapping subproblems
            key = (i, j, length)
            if key in dp:
                return dp[key]
            
            # greedy to find the possible max digit from nums1 and nums2
            # 1) bigger digit in the higher position of the number will get bigger number
            # 2) at the same time, we need to ensure that we still have enough digits to form a number with "length" digits
            
            # try to find the possible max digit from index i in nums1
            index1 = None
            for ii in range(i, m):
                if (m - ii + n - j) < length:
                    break
                if index1 is None or nums1[index1] < nums1[ii]:
                    index1 = ii
            
            # try to find the possible max digit from index j in nums2
            index2 = None
            for jj in range(j, n):
                if (m - i + n - jj) < length:
                    break
                if index2 is None or nums2[index2] < nums2[jj]:
                    index2 = jj
                    
            maxNumberStr = None
            if index1 is not None and index2 is not None:
                if nums1[index1] > nums2[index2]:
                    maxNumberStr = str(nums1[index1]) + getMaxNumberString(index1 + 1, j, length - 1)
                elif nums1[index1] < nums2[index2]:
                    maxNumberStr = str(nums2[index2]) + getMaxNumberString(i, index2 + 1, length - 1)
                else:
                    # get the same digit from nums1 and nums2, so need to try two cases and get the max one 
                    maxNumberStr = max(str(nums1[index1]) + getMaxNumberString(index1 + 1, j, length - 1), str(nums2[index2]) + getMaxNumberString(i, index2 + 1, length - 1))
            elif index1 is not None:
                maxNumberStr = str(nums1[index1]) + getMaxNumberString(index1 + 1, j, length - 1)
            elif index2 is not None:
                maxNumberStr = str(nums2[index2]) + getMaxNumberString(i, index2 + 1, length - 1)
            
            dp[key] = maxNumberStr
            return maxNumberStr

        result_str = getMaxNumberString(0, 0, k)
        
        # number string to digit array
        result = []
        for c in result_str:
            result.append(int(c))
        
        return result
class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        String ans="";
        for (int i = Math.max(0, k-nums2.length); i <= Math.min(nums1.length, k); i++){ // try all possible lengths from each seq
            String one = solve(nums1, i); // find the best seq matching len of i
            String two = solve(nums2, k-i); // len of k-i
            StringBuilder sb = new StringBuilder();
            int a = 0, b = 0;
            while(a < i || b < k-i){ // merge it to the max
                sb.append(one.substring(a).compareTo(two.substring(b))>=0?one.charAt(a++):two.charAt(b++));
            }
            if (sb.toString().compareTo(ans)>0){ // if better, we replace.
                ans=sb.toString();
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < k;++i){
            res[i]=ans.charAt(i)-'0';
        }
        return res;
    }

    private String solve(int[] arr, int k){
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0;i<arr.length;++i){
            while(!stack.isEmpty()&&arr.length-i+stack.size()>k&&stack.peek()<arr[i]){
                stack.pop();
            }
            stack.push(arr[i]);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < k;i++){
            sb.append(stack.pollLast());
        }
        return sb.toString();
    }
}
class Solution {
public:
    vector<int> maxArray(vector<int>&nums,int k){
        int n=nums.size();
        stack<int>seen;
        for(int i=0;i<n;i++){
            int right=n-i-1;
            while(not seen.empty() and seen.top()<nums[i] and right+seen.size()>=k)seen.pop();
            if(seen.size()<k)seen.push(nums[i]);
        }
        vector<int>res(k,0);
        for(int i=res.size()-1;i>=0;i--){
            res[i]=seen.top();
            seen.pop();
        }
        return res;
    }
    bool greater(vector<int>&arr1,int i,vector<int>&arr2,int j){
        for(;i<arr1.size() and j<arr2.size();i++,j++){
            if(arr1[i]==arr2[j])continue;
            return arr1[i]>arr2[j];
        }
        return i!=arr1.size();
    }
    vector<int> merge(vector<int>&arr1,vector<int>&arr2){
        vector<int>res(arr1.size()+arr2.size());
        for(int ind=0,i=0,j=0;ind<res.size();ind++){
            if(greater(arr1,i,arr2,j)){
                res[ind]=arr1[i];
                i++;
            }else{
                res[ind]=arr2[j];
                j++;
            }
        }
        return res;
    }
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int m=nums1.size(),n=nums2.size();
        vector<int>ans;
        for(int len1=max(0,k-n);len1<=min(m,k);len1++){
            int len2 = k-len1;
            vector<int> arr1 = maxArray(nums1,len1);
            vector<int> arr2 = maxArray(nums2,len2);
            vector<int> temp_res = merge(arr1,arr2);
            if(greater(temp_res,0,ans,0)){
                ans.resize(temp_res.size());
                for(int i=0;i<temp_res.size();i++){
                    ans[i]=temp_res[i];
                }
            }
        }
        return ans;
    }
};
const maxNumber = (a, b, k) => {
    let m = a.length, n = b.length;
    let res = [];
    for (let i = Math.max(0, k - n); i <= Math.min(k, m); i++) {
        let maxA = maxArray(a, i), maxB = maxArray(b, k - i);
        let merge = mergeArray(maxA, maxB);
        if (merge > res) res = merge;
    }
    return res;
};

const maxArray = (a, k) => {
    let drop = a.length - k, res = [];
    for (const x of a) {
        while (drop > 0 && res.length && res[res.length - 1] < x) {
            res.pop();
            drop--;
        }
        res.push(x);
    }
    if (res.length >= k) {
        res = res.slice(0, k);
    } else {
        res = res.concat(Array(k - res.length).fill(0));
    }
    return res;
};

const mergeArray = (a, b) => {
    let res = [];
    while (a.length + b.length) res.push(a > b ? a.shift() : b.shift())
    return res;
};
Create Maximum Number