Maximum score of a node sequence

Array Graph Theory Sorting Enumeration

39.8% acceptance

Feb 25, 2026

579

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. Return the maximum score of a valid node sequence with a length of 4. If no such sequence exists, return -1.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_score(scores: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
    let n = scores.len();
    // For each node, keep top 3 neighbors by score
    let mut top: Vec<Vec<usize>> = vec![Vec::new(); n];
    for e in &edges {
      let (u, v) = (e[0] as usize, e[1] as usize);
      top[u].push(v);
      top[v].push(u);
    }
    // Sort each neighbor list by score desc, keep top 3
    for i in 0..n {
      top[i].sort_by(|&a, &b| scores[b].cmp(&scores[a]));
      top[i].truncate(3);
    }

    let mut ans = -1i32;
    for e in &edges {
      let (u, v) = (e[0] as usize, e[1] as usize);
      // Try all combinations of best neighbor a of u (a != v) and b of v (b != u, b != a)
      for &a in &top[u] {
        if a == v { continue; }
        for &b in &top[v] {
          if b == u || b == a { continue; }
          let total = scores[u] + scores[v] + scores[a] + scores[b];
          ans = ans.max(total);
        }
      }
    }
    ans
  }
}