Create Maximum Number - Solution & Explanation

Problem Overview: You are given two arrays of digits and an integer k. Pick digits from both arrays to build the largest possible number of length k, while preserving the relative order of digits within each array. The challenge is deciding how many digits to take from each array and merging them so the final sequence is lexicographically maximum.

Approach 1: Greedy Combine Method (Greedy + Monotonic Stack) (Time: O((n+m)k), Space: O(k))

This approach breaks the problem into two subproblems: selecting the best subsequence from each array and merging them optimally. For every possible split where you take i digits from nums1 and k-i from nums2, compute the maximum subsequence of that length using a monotonic decreasing stack. While iterating through the array, pop smaller digits from the stack if you still have removals available so larger digits can appear earlier.

Once both subsequences are built, merge them greedily. At each step compare the remaining suffixes of both sequences and append the lexicographically larger one. This comparison ensures the final number stays globally optimal instead of locally greedy. The algorithm iterates through all valid splits, generates candidate numbers, and keeps the maximum result. This technique heavily uses ideas from greedy algorithms, stack, and monotonic stack patterns.

Approach 2: Dynamic Programming Approach (Time: O(n*m*k), Space: O(n*m*k))

The dynamic programming formulation tracks the best possible sequence formed using prefixes of both arrays. Define a DP state representing the best number you can form using the first i elements of nums1, the first j elements of nums2, and building a sequence of length t. From each state, decide whether to take the next digit from nums1 or nums2, updating the lexicographically maximum result.

This approach guarantees correctness but becomes expensive because each state stores or compares sequences. The number of states grows with n × m × k, and merging candidate sequences is costly. While useful for understanding the decision structure, it is rarely used in production solutions due to memory and runtime overhead.

Recommended for interviews: The greedy monotonic stack + merge method is the expected solution. Interviewers want to see that you can decompose the problem: generate maximum subsequences, then merge them with lexicographic comparison. Mentioning the brute-force split and explaining why the stack-based subsequence extraction works shows strong reasoning with array and greedy patterns.