Hard · Graphs

Maximum Score of a Node Sequence

Given an undirected graph with node scores scores[i] and an edge list, return the maximum total score of a sequence of four distinct nodes in which every two consecutive nodes are joined by an edge, or −1 if no such sequence exists.

Examples

Example 1

{
  "scores": [5, 2, 9, 8, 4],
  "edges": [
    [0, 1],
    [1, 2],
    [2, 3],
    [0, 2],
    [1, 3],
    [2, 4]
  ]
}

Output: score 24

Example 2

{
  "scores": [5, 2, 9, 1],
  "edges": [
    [0, 1],
    [1, 2],
    [2, 3],
    [0, 3]
  ]
}

Output: score 17

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.