Greedy Algorithms8 sections · 316 units
Open in Course

Create Maximum - Subproblems

Three greedy steps

Break the problem into three parts:

1.1. Select i digits from nums1, k-i digits from nums2.: Try all valid splits.

2.2. Get max number of length m from one array.: Use monotonic stack (similar to Remove K Digits).

3.3. Merge two arrays into max number.: At each step, pick the lexicographically larger suffix. Combine: try all splits, merge each pair, keep the maximum result. The lexicographically larger suffix comparison in merging means: if nums1[i:]nums1[i:] > nums2[j:]nums2[j:] as arrays, pick from nums1nums1. This tie-breaking rule ensures maximum result when both arrays have the same leading digit.