Maximum Score of a Node Sequence
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. You are also given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.
A node sequence is valid if it meets the following conditions:
- There is an edge connecting every pair of adjacent nodes in the sequence.
- No node appears more than once in the sequence.
The score of a node sequence is defined as the sum of the scores of the nodes in the sequence.
Return the maximum score of a valid node sequence with a length of 4. If no such sequence exists, return -1.
Example 1
Input
scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]Output
24The chosen valid node sequence [0,1,2,3] has score 5 + 2 + 9 + 8 = 24, and no valid sequence has a greater score.
Example 2
Input
scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]]Output
-1There are no valid node sequences of length 4, so the answer is -1.
Constraints
- n == scores.length
- 4 <= n <= 5 * 10^4
- 1 <= scores[i] <= 10^8
- 0 <= edges.length <= 5 * 10^4
- edges[i].length == 2
- 0 <= ai, bi <= n - 1
- ai != bi
- There are no duplicate edges.