Problem statement

https://leetcode.com/problems/get-the-maximum-score/

Solution

The question actually asks to find path with longest weight in DAG, which can be done with dp. Also we can add two dummy variables [-1] for start and [-2] for end, so then we need to add 3 to the final answer.

Complexity

Time complexity is O(n), space as well to construct graph.

Code

class Solution:
    def maxSum(self, A1, A2):
        A1 = [-1] + A1 + [-2]
        A2 = [-1] + A2 + [-2]
        
        graph = defaultdict(list)
        for x, y in chain(zip(A1, A1[1:]), zip(A2, A2[1:])):
            graph[x].append(y)

        @lru_cache(None)
        def dp(num):
            return num + max([dp(i) for i in graph[num]] or [0])
        
        return (dp(-1) + 3) % (10**9 + 7)