Topological Sort O(M + N)
Since the arrays are stricly increasing, there are no duplicates within each array. So we can create a DAG where every node is a number. After that, we can do a
Since the arrays are stricly increasing, there are no duplicates within each array. So we can create a DAG where every node is a number. After that, we can do a top sort on that graph and track the path with the greatest sum in the dists dictionary. dists[num] = the max score to get to the node num.\n\n```\nclass Solution:\n    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n        indeg = defaultdict(int)\n        g = defaultdict(list)\n        \n        for i in range(len(nums1)-1):\n            g[nums1[i]].append(nums1[i+1])\n            indeg[nums1[i+1]] += 1\n        for i in range(len(nums2)-1):\n            g[nums2[i]].append(nums2[i+1])\n            indeg[nums2[i+1]] += 1\n        \n        q = deque()\n        ans = 0\n        dists = defaultdict(int)\n        for num in g:\n            if indeg[num] == 0:\n                q.append((num, num))\n                dists[num] = num\n        \n        while q:\n            num, score = q.popleft()\n            ans = max(ans, score)\n            for nei in g[num]:\n                indeg[nei] -= 1\n                dists[nei] = max(dists[nei], score)\n                if indeg[nei] == 0:\n                    q.append((nei, nei + dists[nei]))\n        return ans % (10**9+7)\n```
[]