Maximum Score of a Node Sequence — LeetCode 2242 Python Solution

The problem

There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 0-indexed integer array scores of length n where scores[i] denotes the score of node i.

Example

Input

scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]

Output

24

Explanation

The figure above shows the graph and the chosen node sequence [0,1,2,3].

Python solution

class Solution:
    def maximumScore(self, scores: List[int], edges: List[List[int]]) -> int:
        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        for k in g.keys():
            g[k] = nlargest(3, g[k], key=lambda x: scores[x])
        ans = -1
        for a, b in edges:
            for c in g[a]:
                for d in g[b]:
                    if b != c != d != a:
                        t = scores[a] + scores[b] + scores[c] + scores[d]
                        ans = max(ans, t)
        return ans

Complexity

Pattern: Depth-First Search

Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 2242. Maximum Score of a Node Sequence is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Graph.

The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.

Related problems