Python - Top Down DP - O(N) Time, O(N) Space
Recursively choose the maximum between staying on the same track and switching to a different track. Switching to a different track (track ^ 1) is possible only
Recursively choose the maximum between staying on the same track and switching to a different track. Switching to a different track (`track ^ 1`) is possible only when the same value exists on a different track (`track ^ 1`).\n\nTime complexity: O(N)\nSpace complexity: O(N)\n```py\n\nfrom sys import setrecursionlimit\nsys.setrecursionlimit(1_000_000)\n\nclass Solution:\n    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:\n        # build index map for nums1 and nums2\n        index_map = {}\n        for i, num in enumerate(nums1):\n            index_map[(num, 0)] = i\n        for i, num in enumerate(nums2):\n            index_map[(num, 1)] = i\n        \n        @functools.lru_cache(None)\n        def helper(idx, track):\n            if (track == 0 and idx == len(nums1)) or (track == 1 and idx == len(nums2)):\n                return 0\n            val = nums1[idx] if track == 0 else nums2[idx]\n            res = val + helper(idx + 1, track) # same track\n            if (val, track ^ 1) in index_map: # different track\n                other_idx = index_map[(val, track ^ 1)]\n                res = max(res, val + helper(other_idx + 1, track ^ 1))\n                \n            return res\n        \n        return max(helper(0, 0), helper(0, 1)) % (10**9 + 7)\n\n```
[]