Monotonic Stack + Two Pointers | C++
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves creating the maximum possible number by selecting a subsequence fr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves creating the maximum possible number by selecting a subsequence from two given arrays while maintaining the relative order of elements. The idea is to use a greedy approach to find the maximum subsequence from each array independently and then merge them optimally to form the final result.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Extract Maximum Subsequences**: Use a greedy algorithm to find the maximum subsequence of a given length from each array.\n2. **Merge Subsequences**: Merge the two subsequences to form the maximum possible number by comparing elements and maintaining the relative order.\n3. **Iterate for All Combinations**: Iterate over all possible lengths of subsequences from both arrays to ensure we cover all combinations that sum up to `k`.\n\n# Complexity\n- **Time complexity:** The overall time complexity is $$O((n1 + n2) * k^2)$$ where `n1` and `n2` are the lengths of `nums1` and `nums2` respectively. This is due to the nested loops and the greedy subsequence extraction and merging steps.\n\n- **Space complexity:** The space complexity is $$O(k)$$, required to store the subsequences and the result.\n\n# Code\n```cpp\nint init = [](){\n    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);\n    return -1;\n}();\n\nclass Solution {\npublic: \n    vector<int> getMaxSubsequence(vector<int>& nums, int k) {\n        int n = nums.size();\n        vector<int> ans;\n        for (int i = 0; i < n; ++i) {\n            while (!ans.empty() && ans.back() < nums[i] && ans.size() + n - i - 1 >= k) \n                ans.pop_back();\n            if (ans.size() < k) \n                ans.push_back(nums[i]);\n        }\n        return ans;\n    }\n    \n    bool isGreater(vector<int> &word1, vector<int> &word2, int i, int j) {\n        while (i < word1.size() && j < word2.size()) {\n            if (word1[i] > word2[j]) \n                return true;\n            else if (word1[i] < word2[j]) \n                return false;\n            i++, j++;\n        }\n        return i != word1.size();\n    }\n\n    vector<int> merge(vector<int> &a, vector<int> &b) {\n        vector<int> ans;\n        int i = 0, j = 0;\n        while (i < a.size() && j < b.size()) {\n            if (a[i] > b[j]) \n                ans.push_back(a[i++]);\n            else if (a[i] < b[j]) \n                ans.push_back(b[j++]);\n            else {\n                if (isGreater(a, b, i, j)) \n                    ans.push_back(a[i++]);\n                else \n                    ans.push_back(b[j++]); \n            }\n        }\n        while (i < a.size()) \n            ans.push_back(a[i++]);\n        while (j < b.size()) \n            ans.push_back(b[j++]);\n        return ans;\n    }\n\n    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {\n        vector<int> ans(k, 0);\n        int n1 = nums1.size(), n2 = nums2.size();\n        for (int i = max(0, k - n2); i <= min(k, n1); ++i) {\n            if (i > n1 || k - i > n2) \n                continue;\n            vector<int> a = getMaxSubsequence(nums1, i);\n            vector<int> b = getMaxSubsequence(nums2, k - i);\n            vector<int> tmp = merge(a, b);\n            if (isGreater(tmp, ans, 0, 0)) \n                ans = tmp;\n        }\n        return ans;\n    }\n};\n```
['Array', 'Two Pointers', 'Stack', 'Greedy', 'Monotonic Stack', 'C++']