[Python] O(n) 600ms solution: use common numbers of two arrays (Heavily Commented)
The basic idea behind this solution is to find the common numbers (and the index) of the two arrays and always pick the larger sum of each interval between comm
The basic idea behind this solution is to find the common numbers (and the index) of the two arrays and always pick the larger sum of each interval between common number\'s of the two arrays.\n\n```\nclass Solution:\n    def maxSum(self, a1: List[int], a2: List[int]) -> int:\n        if a1[0] >= a2[-1]: return sum(a1)\n        if a2[0] >= a1[-1]: return sum(a2)\n        \n        # the position of each number in a1 and a2\n        a1_d = dict(zip(a1, range(len(a1))))\n        a2_d = dict(zip(a2, range(len(a2))))\n        \n        # the common number in both a1 and a2:\n        # e.g. [2,4,5,8,10] and [4,6,8,9]\n        # common will be [8, 4]\n        common = sorted(set(a1) & set(a2), reverse = True)\n        \n        # Edge case: if no common elements, return the max sum of a1 or a2\n        if not common: \n            return max(sum(a1), sum(a2))\n        \n        # from the last common number, sum that index till the tail\n        ret = max( sum(a1[a1_d[common[0]]:]), sum(a2[a2_d[common[0]]:]))\n        after = common[0]\n        \n        # for each interval of two common number, use the bigger sum, adding to the result\n        for c in common[1:]:\n            ret += max( sum(a1[a1_d[c]:a1_d[after]]), sum(a2[a2_d[c]:a2_d[after]]) )\n            after = c\n            \n        # Finally, from the head to the first common number\n        ret += max( sum(a1[:a1_d[after]]), sum(a2[:a2_d[after]]) )\n        return ret % (10 ** 9 + 7)\n```
['Python']