interesting problem
Intuition\n Describe your first thoughts on how to solve this problem. \n\nThe problem requires finding the largest possible number of length k formed by combin
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nThe problem requires finding the largest possible number of length `k` formed by combining two arrays while preserving the relative order of elements in each array. My intuition is to break the problem into smaller parts: select subsequences from both arrays and then merge them while maintaining the lexicographical order.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nHigh-Level Approach:\n1. **Determine the Number of Digits to Take from Each Array:**\n    - Iterate over all possible ways to split `k` between `n1` (first array) and `n2` (second array). This means we decide how many elements to pick from `n1` and how many from `n2` such that the sum is equal to `k`.\n    - For each split, we will attempt to pick the largest possible subsequence of digits from `n1` and `n2` using a helper function.\n    \n2. **Select the Maximum Subsequence from an Array:**\n    - To pick the maximum subsequence of a given length from a single array, we use a greedy approach with a stack. We iterate over the array and maintain a stack of the maximum digits by removing smaller digits that could be replaced by larger ones later in the array, while ensuring we select exactly the required number of digits.\n    \n3. **Merge the Two Subsequences:**\n    - After selecting subsequences from both arrays, we need to merge them into a single sequence. At each step, we pick the larger of the leading elements from the two subsequences. This ensures that the resulting sequence is as lexicographically large as possible.\n    \n4. **Compare and Keep the Maximum Number:**\n    - As we generate different combinations of subsequences and merge them, we compare the resulting numbers and keep the one that is lexicographically the largest. This ensures that by the end, we have the maximum possible number.\n\nLet\'s delve into each step in detail.\n\n# Complexity\n- **Time complexity:**  \n    The time complexity is $$O(k \\cdot (n + m))$$, where `n` and `m` are the lengths of the two input arrays. For each split of `k` (up to `k` times), we calculate subsequences from both arrays, which takes linear time with respect to the size of each array. Additionally, merging the subsequences also takes linear time.\n\n- **Space complexity:**  \n    The space complexity is $$O(n + m)$$ because we need space to store the subsequences and the merged results.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> maxSeq(vector<int>& n1, int n) {\n        int del = n1.size() - n;\n        stack<int> stc;\n\n        for (int i = 0; i < n1.size(); i++) {\n            while (del > 0 and !stc.empty() and stc.top() < n1[i]) {\n                stc.pop();\n                del--;\n            }\n            stc.push(n1[i]);\n        }\n\n        vector<int> ans;\n        int extra = stc.size() - n;\n        while (!stc.empty() and extra--)\n            stc.pop();\n        while (!stc.empty()) {\n            ans.push_back(stc.top());\n            stc.pop();\n        }\n\n        reverse(ans.begin(), ans.end());\n        return ans;\n    }\n\n    bool isGreater(vector<int>& a, int i, vector<int>& b, int j) {\n        while (i < a.size() && j < b.size()) {\n            if (a[i] > b[j])\n                return true;\n            if (a[i] < b[j])\n                return false;\n            i++;\n            j++;\n        }\n        return (a.size() - i) > (b.size() - j);\n    }\n\n    vector<int> merge(vector<int>& a, vector<int>& b) {\n        int i = 0, j = 0;\n        vector<int> merged;\n        while (i < a.size() || j < b.size()) {\n            if (isGreater(a, i, b, j)) {\n                merged.push_back(a[i++]);\n            } else {\n                merged.push_back(b[j++]);\n            }\n        }\n        return merged;\n    }\n\n    vector<int> maxNumber(vector<int>& n1, vector<int>& n2, int k) {\n        int n = n1.size(), m = n2.size();\n        vector<int> ans(k, -1), temp;\n\n        for (int i = 0; i <= k; i++) {\n            // sub-sequence from n1=i, from n2=k-i\n            vector<int> s1 = maxSeq(n1, i);\n            vector<int> s2 = maxSeq(n2, k - i);\n\n            temp = merge(s1, s2);\n            if (temp.size() < k)\n                continue;\n\n            if (isGreater(temp, 0, ans, 0))\n                ans = temp;\n        }\n\n        return ans;\n    }\n};\n```
['Array', 'Two Pointers', 'Stack', 'Greedy', 'Monotonic Stack', 'C++']