C++  DP+greedy Solution should be easy to understand
Here is the idea:\n                       \nLet's consider a similar but simple version of this problem: if there is only one array arr of which length is m, ho
Here is the idea:\n                       \nLet's consider a similar but simple version of this problem: if there is only one array arr of which length is m, how to find the k digits of it to create maximum number preserving the order?\nSo here comes to my DP solution: DP[ i ][ j ] means that the maximum number that has i digits we can get  when the jth digits is the last one of this number. Thus the formula is as follows:\n\n           dp[ i ] [ j ] = max(dp[ i ][ j ], max(dp[ i - 1 ][ 0 ... j - 1 ]))\n\nOk. We apply this formula to the two given arrays and then get two DP arrays DP1 and DP2 where DP[ i ] means the largest number with i digits.    \n\nBack to our problem: Choose k digits of these two arrays/strings to create the maximum number. Now here is the greedy solution:\n\nFor every pair of i and j where i + j == k and i is the number of digits used from array1 and j is the number of digits used from array2, we have to combine to create a new number so that it is the largest of all combinations. Remember a similar greedy problem? The trick here is that we use two pointers for each array and in each iteration, pick up pointers pointing to the larger digit or the larger substring. Then the number created is the largest from the given two arrays/strings.\n                    \nStill confused? Plsz read the code below:\n      \n    \n              \n    class Solution {\n        public:\n            vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {\n                vector<int> ans;\n                if(!nums1.size() && !nums2.size() || !k)\n                    return ans;\n                ans.resize(k);\n                int n = nums1.size(), m = nums2.size();\n                vector<string> dp1(min(k, n)), dp2(min(k, m));\n                vector<string> dpprev1(n), dpcur1(n), dpprev2(m), dpcur2(m);\n        \n                for(int i = 0; i < dp1.size(); ++ i){\n                    string tmpval(i + 1, 0);\n                    dp1[i] = tmpval;\n                    if(!i){\n                        for(int j = 0; j < n; ++ j){\n                            dpprev1[j] = "";\n                            dpprev1[j] += (char)(nums1[j] + '0');\n                            dp1[i] = max(dp1[i], dpprev1[j]);\n                            if(j)\n                                dpprev1[j] = max(dpprev1[j], dpprev1[j - 1]);\n        \n                        }\n                    }else{\n                        for(int j = i; j < n; ++ j){\n                            dpcur1[j] = tmpval;\n        \n                            dpcur1[j] = max(dpcur1[j], dpprev1[j - 1] + (char)(nums1[j] + '0'));\n        \n                            dp1[i] = max(dp1[i], dpcur1[j]);\n                            if(j >= i)\n                                dpcur1[j] = max(dpcur1[j], dpcur1[j - 1]);\n                        }\n                        dpprev1 = dpcur1;\n                    }\n        \n                }\n        \n        \n        \n                for(int i = 0; i < dp2.size(); ++ i){\n                    string tmpval(i + 1, 0);\n                    dp2[i] = tmpval;\n                    if(!i){\n                        for(int j = 0; j < m; ++ j){\n                            dpprev2[j] = "";\n                            dpprev2[j] += (char)(nums2[j] + '0');\n                            dp2[i] = max(dp2[i], dpprev2[j]);\n                            if(j)\n                                dpprev2[j] = max(dpprev2[j], dpprev2[j - 1]);\n                        }\n                    }else{\n                        for(int j = i; j < m; ++ j){\n                            dpcur2[j] = tmpval;\n        \n                            dpcur2[j] = max(dpcur2[j], dpprev2[j - 1] + (char)(nums2[j] + '0'));\n        \n                            dp2[i] = max(dp2[i], dpcur2[j]);\n                            if(j >= i)\n                                dpcur2[j] = max(dpcur2[j], dpcur2[j - 1]);\n                        }\n                        dpprev2 = dpcur2;\n                    }\n        \n                }\n        \n        \n                string tmpans(k, 0), v = "";\n        \n                if(!dp1.size()){\n                    getAns(v, dp2[k - 1], ans, tmpans);\n                }else{\n                    for(int i = 0; i <= min(k, (int)dp1.size()); ++ i){\n                        if(i == 0){\n                            if(dp2.size() >= k)\n                                getAns(v, dp2[k - 1], ans, tmpans);\n                        }else if(i < k){\n                            if(dp2.size() >= k - i)\n                                getAns(dp1[i - 1], dp2[k - i - 1], ans, tmpans);\n                        }else{\n                            if(dp1.size() >= k)\n                                getAns(dp1[k - 1], v, ans, tmpans);\n                        }\n                    }\n        \n                }\n        \n                return ans;\n            }\n        \n        private:\n            void getAns(string &s1, string &s2, vector<int> &ans, string &tmpans){\n                string res;\n                if(!s1.size())\n                    res = s2;\n                else if(!s2.size())\n                    res = s1;\n                else{\n                    int id1 = 0, id2 = 0;\n        \n                    while(id1 < s1.size() && id2 < s2.size()){\n                        if(s1[id1] > s2[id2]){\n                            res += s1[id1 ++];\n                        }else if(s1[id1] < s2[id2]){\n                            res += s2[id2 ++];\n                        }else{\n                            if(s1.substr(id1) >= s2.substr(id2))\n                                res += s1[id1 ++];\n                            else\n                                res += s2[id2 ++];\n                        }\n                    }\n                    while(id1 < s1.size())\n                        res += s1[id1 ++];\n                    while(id2 < s2.size())\n                        res += s2[id2 ++];\n                }\n        \n                if(res > tmpans){\n                    tmpans = res;\n                    for(int i = 0; i < res.size(); ++ i)\n                        ans[i] = (res[i] - '0');\n                }\n            }\n        };
['Dynamic Programming', 'Greedy', 'C++']