LeetCode-2242 节点序列的最大得分

LeetCode-2242 节点序列的最大得分 #

Solution 1 #

要找出长度为 $4$ 的节点序列的最大的得分, 考虑枚举中间这条边, 再查看左右两个端点的可能性. 注意需要符合端点不重复的规则 .

class Solution:
    def maximumScore(self, scores: List[int], edges: List[List[int]]) -> int:
        n = len(scores)
        e = {i: [] for i in range(n)}

        for a, b in edges:
            e[a].append(b)
            e[b].append(a)

        for i in range(n):
            e[i].sort(key=lambda x: scores[x], reverse=True)

        ans = 0
        for x, y in edges:
            res = scores[x] + scores[y]

            for i in range(min(3, len(e[x]))):
                for j in range(min(3, len(e[y]))):
                    if e[x][i] != y and e[y][j] != x and e[x][i] != e[y][j]:
                        res += scores[e[x][i]] + scores[e[y][j]]
                        ans = max(ans, res)
                        res -= scores[e[x][i]] + scores[e[y][j]]

        return ans if ans != 0 else -1