✅🔥 | Java Solution | Explained | ✅🔥
Intuition - \nThe problem requires finding the maximum number that can be formed by selecting k elements from two input arrays, nums1 and nums2. The elements sh
# Intuition - \nThe problem requires finding the maximum number that can be formed by selecting k elements from two input arrays, nums1 and nums2. The elements should maintain their relative order within each array. The solution involves dividing the problem into smaller subproblems, finding the maximum numbers that can be formed by selecting a certain number of elements from each array, and then merging those numbers to form the overall maximum number.\n\n# Approach - \n1. Initialize the result array of size k to store the maximum number.\n2. Iterate over the number of elements (i) to be selected from nums1, which ranges from 0 to the minimum of k and the length of nums1.\n   - Calculate the corresponding number of elements (j) to be selected from nums2, which is equal to k - i.\n   - Find the maximum subsequence of length i from nums1 using the `findMax` function.\n   - Find the maximum subsequence of length j from nums2 using the `findMax` function.\n   - Merge the two subsequences obtained from nums1 and nums2 using the `merge` function.\n   - If the merged sequence is greater than the current result, update the result to the merged sequence.\n3. Return the resulting maximum number.\n\n# Complexity Analysis - \nLet n be the length of nums1 and m be the length of nums2.\n- The overall **time complexity of the solution is O((n + m)^3)** since we have three nested loops: one for iterating over the number of elements to be selected from nums1, one for iterating over the elements of nums1 and nums2 in the `merge` function, and one for iterating over the elements of nums in the `findMax` function.\n- The **space complexity is O(k)** since we are using a result array of size k to store the maximum number.\n\n# Code\n```\npublic class Solution {\n    public int[] maxNumber(int[] nums1, int[] nums2, int k) {\n        int[] result = new int[k];\n        for (int i = Math.max(0, k - nums2.length); i <= Math.min(nums1.length, k); i++) {\n            int j = k - i;\n            int[] part1 = findMax(nums1, i);\n            int[] part2 = findMax(nums2, j);\n            int[] cand = merge(part1, part2);\n            if (greater(cand, 0, result, 0)) {\n                result = cand;\n            }\n        }\n        return result;\n    }\n\n    private boolean greater(int[] nums1, int start1, int[] nums2, int start2) {\n        while (start1 < nums1.length && start2 < nums2.length && nums1[start1] == nums2[start2]) {\n            start1++;\n            start2++;\n        }\n        return start2 == nums2.length || (start1 < nums1.length && nums1[start1] > nums2[start2]);\n    }\n\n    private int[] merge(int[] nums1, int[] nums2) {\n        int[] result = new int[nums1.length + nums2.length];\n        int i = 0, j = 0, k = 0;\n        while (i < nums1.length && j < nums2.length) {\n            if (greater(nums1, i, nums2, j)) {\n                result[k++] = nums1[i++];\n            } else {\n                result[k++] = nums2[j++];\n            }\n        }\n        while (i < nums1.length) {\n            result[k++] = nums1[i++];\n        }\n        while (j < nums2.length) {\n            result[k++] = nums2[j++];\n        }\n        return result;\n    }\n\n    private int[] findMax(int[] nums, int k) {\n        int[] result = new int[k];\n        int j = 0;\n        for (int i = 0; i < nums.length; i++) {\n            while (j > 0 && result[j - 1] < nums[i] && j + nums.length - i > k) {\n                j--;\n            }\n            if (j < k) {\n                result[j++] = nums[i];\n            }\n        }\n        return result;\n    }\n}\n```
['Stack', 'Greedy', 'Monotonic Stack', 'Java']