[2 Solutions] DFS + Greedy with thought process when being asked during interviews
DFS\nBecause we should go through the path from left to the right, which makes it look like tree traversal, but not fully the same. However, it gives us an insi
### DFS\nBecause we should go through the path from left to the right, which makes it look like tree traversal, but not fully the same. However, it gives us an insight that we can convert it to graph problem asking the maximum sum of path from root to leaves.\nThe graph is constructed by simply conneting adjacent integers and the common integers in both arrays.\n\u200B\nNote that we are constructing directed graph,but there is a circle between the common integers, so we need use `parent` to avoid circle traversal.\n\u200B\nThe next problem for this solution is that we have the same integers for different nodes, but we can resolve it by reverting the integer for the `nums2` and remember to use absolute value when calculating the sum value.\n\u200B\nThe final problem we have to deal with is that the sum value only care about distinct integers, so we need discard the integer when we swith from one array to the other.\n\nFinally, we just run post order traversal on the graph to return the maximum sum of path on the subgraph.\n\u200B\nBecause there could be 2 parents for one single node, we have to use `cache` to store the immediate results for reducing time complexity.\n\n```python\ndef maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n\tgraph = defaultdict(list)\n\tfor a, b in zip(nums1, nums1[1:]):\n        graph[a].append(b)\n\tfor a, b in zip(nums2, nums2[1:]):\n\t\tgraph[-a].append(-b)\n        \n\tindices2 = set(nums2)\n\tfor i, num in enumerate(nums1):\n\t\tif num in indices2:\n\t\t\tgraph[num].append(-num)\n            graph[-num].append(num)\n\n\t@cache\n\tdef helper(node, parent):\n\t\tans = 0\n\t\tfor nei in graph[node]:\n\t\t\tif parent != nei:\n\t\t\t\tans = max(ans, helper(nei, node) if abs(nei) != abs(node) else helper(nei, node) - abs(node))\n\t\treturn ans + abs(node)\n\treturn max(helper(nums1[0], 0), helper(-nums2[0], 0)) % (10 ** 9 + 7)\n```\n\n### Greedy + Prefix Sum\nThe property of counting the value of distinct integers only indicates that we can merge the common integer as one node so that we can partition the whole arrays as pieces among which there is no common integers. As such, the sum of integers of each piece is fixed and valid because each array has distinct integers, which denotes to a greedy solution iterating each piece and pick the larger one.\nWe can simply iterate each integer on the piece and calculate the sum, and jump to next common merged node after making decisions. However, we can simpify the implementation using prefix sum with pair of indices of common integers between the 2 arrays.\nLet\'s put it all together.\n1. calculate prefix sum for each `nums`.\n2. find out all of pairs of common integers with the indices.\n3. Iterate each pair and sum up the larger sum using prefix sum.\n\n```python\n    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n        pre1, pre2 = [0], [0]\n        for num in nums1:\n            pre1.append(pre1[-1] + num)\n        for num in nums2:\n            pre2.append(pre2[-1] + num)\n        pairs = []\n        indices2 = {num:i for i, num in enumerate(nums2)}\n        for i, num in enumerate(nums1):\n            if num in indices2:\n                pairs.append((i, indices2[num]))\n        total = 0\n        last_i = last_j = -1\n        for i, j in pairs + [(len(nums1), len(nums2))]:          \n            total += max(pre1[i] - pre1[last_i + 1], pre2[j] - pre2[last_j + 1])\n            if i < len(nums1):\n                total += nums1[i]\n            last_i, last_j = i, j\n        return total % (10 ** 9 + 7) \n```\n\n*Time Complexity* = **O(M + N)**\n*Space Complexity* = **O(M+ N)**
['Greedy', 'Depth-First Search', 'Prefix Sum']