Intuitive | Beginner Friendly Explanation✅| C++ | Stack
Intuition\nThe intuition idea is that to create a number of length k, we will take some subsequnce of length k1 from nums1, and of length k2 = ( k- k1 )from num
# Intuition\nThe intuition idea is that to create a number of length `k`, we will take some subsequnce of length `k1` from `nums1`, and of length `k2 = ( k- k1 ) `from `nums2`, since we have to preseve the order of digits from each array it is optimal to select the largest possible subsequnce from each array.\n\nNow we have the largest subsequence possible from both arrays (with `k1` and `k2` digits respectively)\nNow we will merge them to create the largest number possible of `k1 + k2 = k` digits.\n\nWe will try all possible combinations of `k1` and `k2` and return the maximum number encountered.\n\nNOTE: The above listed two sub-problems are separate problems on leetcode itself, i suggest to solve them first. The problem numbers are `1673` and `1754`.\n\nIf you are able to think how to do these two problems, great. if not please look at the following detailed explanations for each:\n\nhttps://leetcode.com/problems/find-the-most-competitive-subsequence/solutions/5012111/c-beginner-friendly-detailed-explantion-monotonic-stack/\n\nThe above problem is to give the smallest sub-sequence, i have done slight modification in the above code to use it to return largest sub-sequence.\n\nFor largest Merge Problem explanation:\nhttps://leetcode.com/problems/largest-merge-of-two-strings/solutions/5012449/clean-code-beginner-friendly-easy-explanation-two-pointers-c/\n\n\n# Approach\n1. To find the largest possible subsequnce from each array, i have used utility function `largestSubsequence` which takes paramters `nums` and `k` and returns the largest possible subsequnce of length `k` in `nums`\n\n2. After getting the largest subsequnce  (of lengths `k1` and `k2`) from each array we will need to merge them to get our desired number of length `k`, the `largestMerge` function does the same\n\n3. Store the maximum of all the merged numbers encountered in the process and retutn it.\n\n\nSee the commented code for more clarity\n\n# Complexity\n- Time complexity:\n$$O(k*(m+n))$$\n\n- Space complexity:\n$$O(m+n)$$\n\n# Code\n```\nclass Solution {\n    string largestSubsequence(vector<int>& nums, int k){\n        string ans = "";\n        int n = nums.size();\n        for(int i = 0; i < n; i++){\n            while( n - i > k - ans.size() && !ans.empty() && ans.back() - \'0\' < nums[i] )\n                ans.pop_back(); \n            if( ans.size() < k )\n                ans += to_string(nums[i]);\n        }\n        return ans;\n    }\n\n    string largestMerge(string word1, string word2) {\n        string ans = "";\n        int i = 0, j = 0, m = word1.length(), n = word2.length();\n        while( i < m && j < n ){\n            if( word1[i] < word2[j] )\n                ans += word2[j++];\n            else if( word1[i] > word2[j] )\n                ans += word1[i++];\n            else{\n                string w1 = word1.substr(i), w2 = word2.substr(j);\n                if( w1 >= w2 )\n                    ans += word1[i++];\n                else\n                    ans += word2[j++];\n            }\n        }\n\n        if( i < m )\n            ans += word1.substr(i);\n        if( j < n  )\n            ans += word2.substr(j);\n\n        return ans;\n    }\n\n    //NOTE: default max function does lexicogrphical comp. on strings\n    //thus custom compare func for integer comparision\n    string maxStr(string str1, string str2){\n        if( str1.length() >  str2.length() )\n            return str1;\n        if( str2.length() > str1.length() )\n            return str2;\n        \n        return max(str1, str2);\n    }\n\npublic:\n    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {\n        int k1 = 0;\n        string ans = "";\n        //try out all possible combinations of k1 and k2\n        while( k1 <= k ){\n            string n1 = largestSubsequence(nums1, k1);\n            string n2 = largestSubsequence(nums2, k - k1);\n\n            ans = maxStr(ans, largestMerge(n1, n2));\n            k1++;\n        }\n\n        //construct the vector from string\n        vector<int> res(ans.begin(), ans.end());\n        \n        //As we create vector from string we get the ASCII values\n        //of each character in our vector\n        //convert it to integer by subtracting 48 as \'0\' = 48 in ASCII\n        for(int i = 0; i < k; i++)\n            res[i] -= 48;\n            \n        return res;\n    }\n};\n```\n\nPLEASE UPVOTE IF THE EXPLANATION WAS HELPFULl\u2764\uFE0F\uD83E\uDD1E
['String', 'Greedy', 'Monotonic Stack', 'C++']