Python 98% faster | Greedy + DP + Segment Tree for Range Query
\n\n\nfrom typing import List\nfrom collections import defaultdict\n\n\nclass Node(object):\n    def __init__(self, beg, end):\n        self.beg = beg\n        
\n\n```\nfrom typing import List\nfrom collections import defaultdict\n\n\nclass Node(object):\n    def __init__(self, beg, end):\n        self.beg = beg\n        self.end = end\n        self.range_max = None\n        self.left = None\n        self.right = None\n\n    def is_leaf(self):\n        return self.beg == self.end\n\n    def __repr__(self):\n        if self.is_leaf():\n            return f"{self.beg}: {self.range_max}"\n        else:\n            return f"{self.beg}~{self.end}: {self.range_max}"\n\n    def query(self, beg, end):\n        # Totally out of range\n        if beg > self.end or end < self.beg:\n            return float("-inf"), -1\n\n        # Query range contains node range\n        elif self.beg >= beg and self.end <= end:\n            return self.range_max\n\n        # Intersection\n        else:\n            return max(self.left.query(beg, end), self.right.query(beg, end))\n\n\ndef build_range_tree(a, beg, end):\n    node = Node(beg, end)\n    if beg == end:\n        node.range_max = (a[beg], -beg)\n    else:\n        mid = (beg + end) // 2\n        node.left = build_range_tree(a, beg, mid)\n        node.right = build_range_tree(a, mid + 1, end)\n        node.range_max = max(node.left.range_max, node.right.range_max)\n\n    return node\n\n\ndef comp_array(a, b, beg_a, beg_b):\n    for i, j in zip(range(beg_a, len(a)), range(beg_b, len(b))):\n        if a[i] > b[j]:\n            return 1\n        elif a[i] < b[j]:\n            return -1\n\n    if len(a) - beg_a > len(b) - beg_b:\n        return 1\n    elif len(a) - beg_a < len(b) - beg_b:\n        return -1\n    else:\n        return 0\n\n\ndef merge_2_arrays(a, b, beg_a, beg_b):\n    ptr1 = beg_a\n    ptr2 = beg_b\n\n    while True:\n        if ptr1 == len(a) or ptr2 == len(b):\n            break\n        comp_res = comp_array(a, b, ptr1, ptr2)\n        if comp_res == 1:\n            yield a[ptr1]\n            ptr1 += 1\n        else:\n            yield b[ptr2]\n            ptr2 += 1\n\n    for i in range(ptr1, len(a)):\n        yield a[i]\n\n    for i in range(ptr2, len(b)):\n        yield b[i]\n\n\ndef pick_k_numbers(a, tree_a, beg_a, k):\n    if k == 0:\n        return []\n    len_a = len(a) - beg_a\n    num_elements_to_drop = len_a - k\n    if num_elements_to_drop == 0:\n        return a[beg_a:]\n\n    end_a = min(beg_a + num_elements_to_drop, len(a) - 1)\n\n    max_val, max_idx = tree_a.query(beg_a, end_a)\n    max_idx = -max_idx\n\n    return [a[max_idx]] + pick_k_numbers(a, tree_a, max_idx + 1, k - 1)\n\n\ndef fetch_dp_table(a, b, tree_a, tree_b, beg_a, beg_b, k, dp_table):\n\n    if k == 0:\n        return []\n\n    if (beg_a, beg_b, k) not in dp_table:\n\n        len_a = len(a) - beg_a\n        len_b = len(b) - beg_b\n\n        num_elements_to_drop = len_a + len_b - k\n\n        if num_elements_to_drop == 0:\n            res = list(merge_2_arrays(a, b, beg_a, beg_b))\n\n        elif len_b == 0:\n            res = pick_k_numbers(a, tree_a, beg_a, k)\n\n        elif len_a == 0:\n            res = pick_k_numbers(b, tree_b, beg_b, k)\n\n        else:\n            end_a = min(beg_a + num_elements_to_drop, len(a) - 1)\n            end_b = min(beg_b + num_elements_to_drop, len(b) - 1)\n\n            max_val_a, max_idx_a = (\n                tree_a.query(beg_a, end_a) if len_a > 0 else (float("-inf"), -1)\n            )\n            max_idx_a = -max_idx_a\n\n            max_val_b, max_idx_b = (\n                tree_b.query(beg_b, end_b) if len_b > 0 else (float("-inf"), -1)\n            )\n            max_idx_b = -max_idx_b\n\n            if max_val_a > max_val_b:\n                next_vals = fetch_dp_table(\n                    a, b, tree_a, tree_b, max_idx_a + 1, beg_b, k - 1, dp_table\n                )\n                res = [max_val_a] + next_vals\n            elif max_val_b > max_val_a:\n                next_vals = fetch_dp_table(\n                    a, b, tree_a, tree_b, beg_a, max_idx_b + 1, k - 1, dp_table\n                )\n                res = [max_val_b] + next_vals\n            else:\n                vala = fetch_dp_table(\n                    a, b, tree_a, tree_b, max_idx_a + 1, beg_b, k - 1, dp_table\n                )\n                valb = fetch_dp_table(\n                    a, b, tree_a, tree_b, beg_a, max_idx_b + 1, k - 1, dp_table\n                )\n                res = [max_val_a] + max(vala, valb)\n\n        dp_table[(beg_a, beg_b, k)] = res\n    else:\n        pass\n\n    return dp_table[(beg_a, beg_b, k)]\n\n\nclass Solution:\n    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n        tree_1 = build_range_tree(nums1, 0, len(nums1) - 1)\n        tree_2 = build_range_tree(nums2, 0, len(nums2) - 1)\n        dp_table = {}\n        res = fetch_dp_table(nums1, nums2, tree_1, tree_2, 0, 0, k, dp_table)\n        return res\n\n\nif __name__ == "__main__":\n    nums1 = [3,4,6,5]\n    nums2 = [9,1,2,5,8,3]\n    k = 5\n    # res = Solution().maxNumber(nums1, nums2, k)\n    # print(res)\n```\n
['Dynamic Programming', 'Python']