#2242
Maximum Score of a Node Sequence
master · 1710 · lc hard +32 · verified · 39.8% accepted · 579 likes · top 19%
Description
Consider an undirected graph with n nodes numbered 0 to n - 1.
You are given a 0-indexed integer array scores of length n where scores[i] is the score of node i, and a 2D integer array edges where edges[i] = [ai, bi] represents an undirected edge.
A valid node sequence satisfies:
- Every pair of consecutive nodes in the sequence shares an edge.
- No node appears more than once.
The sequence's score is the sum of scores of all nodes in it.
Return the maximum score of any valid node sequence of exactly length 4, or -1 if none exists.
Example 1:
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].
The score of the node sequence is 5 + 2 + 9 + 8 = 24.
It can be shown that no other node sequence has a score of more than 24.
Note that the sequences [3,1,2,0] and [1,0,2,3] are also valid and have a score of 24.
The sequence [0,3,2,4] is not valid since no edge connects nodes 0 and 3.
Example 2:
Input: scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]]
Output: -1
Explanation: The figure above shows the graph.
There are no valid node sequences of length 4, so we return -1.
Code
1
2
3