Create Maximum Number

• Define a recursive function, say solve(i, j, l), which aims to find the maximum number of length l using digits from nums1 starting at index i and nums2 starting at index j.
• To prevent recomputing results for the same state (i, j, l), use a 3D array for memoization, memo[i][j][l].
• The base case for the recursion is when the required length l is 0, in which case we return an empty sequence.
• In each recursive call, determine the range of indices to search for the best possible first digit. We can discard a total of (m-i) + (n-j) - l digits from the start of the remaining arrays. This defines the search window.
• Find the maximum digit d within this valid search window in both nums1 and nums2.
• If this maximum digit d is found at multiple positions, we must recursively explore each choice. For each occurrence of d at nums1[p], we form a candidate number by prepending d to the result of solve(p + 1, j, l - 1). Similarly for occurrences in nums2.
• Compare all candidate numbers generated from these recursive calls and select the lexicographically largest one.
• Store this result in the memoization table memo[i][j][l] before returning.

The core of this method is a recursive function, let's call it solve(i, j, l), which is designed to compute the maximum number of length l that can be formed from the subarrays nums1[i:] and nums2[j:].

To select the first digit of the result, we can't just pick any digit. We must ensure that enough digits remain in nums1 and nums2 to form the rest of the number (length l-1). The total number of available digits is (m-i) + (n-j). We can afford to skip (m-i) + (n-j) - l digits. This means we can search for our first digit in nums1[i ... i + d] and nums2[j ... j + d], where d is the number of skippable digits.

We greedily find the largest digit, max_d, in these search windows. A complication arises if max_d appears at multiple positions. For example, if nums1[p1] == max_d and nums2[q1] == max_d, we must recursively find out which choice leads to a better overall number. This means we have to compare the results of d + solve(p1 + 1, j, l - 1) and d + solve(i, q1 + 1, l - 1).

This recursive branching creates overlapping subproblems, as solve might be called with the same (i, j, l) arguments through different paths. A 3D DP table memo[i][j][l] is used to store the results. However, the size of this table, m * n * k, is prohibitively large for the given constraints (500 * 500 * 1000).

• The main function iterates through all possible numbers of digits i to take from nums1. The number of digits from nums2 will then be k-i. The loop for i runs from max(0, k - n) to min(k, m).
• For each i, find the lexicographically largest subsequence of length i from nums1. This is done by a helper function maxSubsequence.
• Similarly, find the largest subsequence of length k-i from nums2.
• Merge the two resulting subsequences into a single candidate array of length k. This is done by a helper function merge.
• The merge function compares the two subsequences element by element. If the current digits are different, it picks the larger one. If they are equal, it must look ahead to see which subsequence is lexicographically greater from the current position onwards.
• Compare the merged candidate with the best result found so far. If the new candidate is larger, update the best result.
• After checking all possible values of i, the best result found is the answer.

maxSubsequence(nums, k) Algorithm:

1. Use a stack-like array stack of size k to build the result.
2. Iterate through nums. For each digit d: a. While the stack is not empty, its top element is smaller than d, and we have enough remaining elements in nums to still form a k-length sequence after popping, pop from the stack. b. If the stack has space, push d onto it.
3. The stack will hold the maximum subsequence.

merge(sub1, sub2) Algorithm:

1. Create a result array merged of size k.
2. Use two pointers, p1 for sub1 and p2 for sub2.
3. In a loop that runs k times, compare the remaining parts of sub1 (from p1) and sub2 (from p2) using a helper isGreater.
4. Append the digit from the greater subsequence to merged and advance its pointer.

This approach breaks the problem down into three main parts: iterating through all possible compositions, finding the maximum subsequence from a single array, and merging two subsequences.

1. Main Loop: We iterate through i, the number of digits to take from nums1. The valid range for i is max(0, k - n) <= i <= min(k, m). For each i, we generate a candidate for the max number and compare it with our current best.

2. maxSubsequence(nums, k): This helper finds the lexicographically largest subsequence of length k. It uses a greedy strategy with a stack. For each number in the input array, we decide whether to push it onto our result stack. We pop from the stack if the current number is larger than the top of the stack, and if popping doesn't prevent us from achieving a k-length result. This ensures our result is as large as possible from left to right.

3. merge(sub1, sub2): This helper combines two subsequences into the largest possible number. It's similar to a standard merge, but when the leading digits of the remaining subsequences are equal, we must perform a lookahead comparison to decide which subsequence to take from. For example, merging [6, 7] and [6, 0, 4], we compare [6, 7] and [6, 0, 4] as a whole. Since 7 > 0, [6, 7] is larger, so we take the 6 from it first.

Here is the Java implementation:

1class Solution {2    public int[] maxNumber(int[] nums1, int[] nums2, int k) {3        int m = nums1.length;4        int n = nums2.length;5        int[] bestResult = new int[0];6 7        for (int i = Math.max(0, k - n); i <= k && i <= m; i++) {8            int[] sub1 = maxSubsequence(nums1, i);9            int[] sub2 = maxSubsequence(nums2, k - i);10            int[] candidate = merge(sub1, sub2);11            if (isGreater(candidate, 0, bestResult, 0)) {12                bestResult = candidate;13            }14        }15        return bestResult;16    }17 18    private int[] maxSubsequence(int[] nums, int k) {19        int n = nums.length;20        int[] stack = new int[k];21        int len = 0;22        for (int i = 0; i < n; i++) {23            while (len > 0 && stack[len - 1] < nums[i] && (n - i) > (k - len)) {24                len--;25            }26            if (len < k) {27                stack[len++] = nums[i];28            }29        }30        return stack;31    }32 33    private int[] merge(int[] nums1, int[] nums2) {34        int k = nums1.length + nums2.length;35        int[] ans = new int[k];36        int i = 0, j = 0, r = 0;37        while (r < k) {38            ans[r++] = isGreater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];39        }40        return ans;41    }42 43    private boolean isGreater(int[] nums1, int p1, int[] nums2, int p2) {44        while (p1 < nums1.length && p2 < nums2.length && nums1[p1] == nums2[p2]) {45            p1++;46            p2++;47        }48        return p2 == nums2.length || (p1 < nums1.length && nums1[p1] > nums2[p2]);49    }50}