# Maximum Score of a Node Sequence
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-score-of-a-node-sequence)
Canonical: https://scaleengineer.com/dsa/problems/maximum-score-of-a-node-sequence
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Graph
---
## Problem
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:**

![](https://assets.glich.co/dsa/maximum-score-of-a-node-sequence/image0.png) 

**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:**

![](https://assets.glich.co/dsa/maximum-score-of-a-node-sequence/image1.png) 

**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.

**Constraints:**

* `n == scores.length`
* `4 <= n <= 5 * 104`
* `1 <= scores[i] <= 108`
* `0 <= edges.length <= 5 * 104`
* `edges[i].length == 2`
* `0 <= ai, bi <= n - 1`
* `ai != bi`
* There are no duplicate edges.

# Approaches
## Brute-force over Middle Edge
This approach considers every edge in the graph as the central edge of a potential 4-node sequence. For each edge `(u, v)`, it exhaustively searches through all neighbors of `u` and `v` to find the other two nodes that complete the sequence and maximize the score.
**Time:** O(sum_{(u,v) in E} (deg(u) * deg(v))). In the worst case, where `deg` is the degree of a node, this can be `O(E * d_max^2)`, where `d_max` is the maximum degree. This can be too slow for the given constraints. · **Space:** O(n + E) for storing the adjacency list, where `n` is the number of nodes and `E` is the number of edges.
**Pros:** Conceptually simpler than the optimized approach.; Correctly finds the maximum score.
**Cons:** Inefficient time complexity, likely to time out on large test cases, especially for graphs with nodes of high degree.
### Explanation
First, we build an adjacency list representation of the graph from the given `edges`. We initialize a variable `maxScore` to -1. We then iterate through every edge `(u, v)` in the input `edges` array. These two nodes will form the middle part of our 4-node sequence `a-u-v-d`. For each edge `(u, v)`, we need to find two other nodes: `a`, a neighbor of `u`, and `d`, a neighbor of `v`. The four nodes `a, u, v, d` must all be distinct. To do this, we use nested loops. The outer loop iterates through all neighbors of `u` (let's call a neighbor `a`). The inner loop iterates through all neighbors of `v` (let's call a neighbor `d`). Inside the inner loop, we check if the four nodes form a valid sequence of distinct nodes: `a != v`, `d != u`, and `a != d`. If they are distinct, we calculate the total score: `scores[a] + scores[u] + scores[v] + scores[d]`. We update `maxScore` with this score if it's higher than the current `maxScore`. After checking all edges and all their neighbor combinations, `maxScore` will hold the result. If no such sequence of length 4 is found, `maxScore` remains -1.

```java
import java.util.*;

class Solution {
    public int maximumScore(int[] scores, int[][] edges) {
        int n = scores.length;
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }

        long maxScore = -1;

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];

            for (int neighborU : adj[u]) {
                if (neighborU == v) continue;
                for (int neighborV : adj[v]) {
                    if (neighborV == u || neighborV == neighborU) continue;
                    
                    long currentScore = (long) scores[u] + scores[v] + scores[neighborU] + scores[neighborV];
                    maxScore = Math.max(maxScore, currentScore);
                }
            }
        }

        return (int) maxScore;
    }
}
```
### Algorithm
- 1. Construct an adjacency list `adj` for the graph.
- 2. Initialize `maxScore = -1`.
- 3. For each edge `(u, v)` in the input `edges` array:
- 4.   For each neighbor `a` of `u`:
- 5.     If `a` is the same as `v`, continue to the next neighbor.
- 6.     For each neighbor `d` of `v`:
- 7.       If `d` is the same as `u` or `a`, continue to the next neighbor.
- 8.       Calculate `currentScore = scores[a] + scores[u] + scores[v] + scores[d]`.
- 9.       Update `maxScore = max(maxScore, currentScore)`.
- 10. Return `maxScore`.

## Optimized Iteration using Top-3 Neighbors
This approach significantly optimizes the search for the two outer nodes of the sequence. It's based on the key insight that for any central edge `(u, v)`, the optimal outer nodes `a` (neighbor of `u`) and `d` (neighbor of `v`) must be among the highest-scoring neighbors of `u` and `v`. Specifically, we only need to consider the top 3 neighbors with the highest scores for each node.
**Time:** O(E * log(d_max) + E). The dominant part is sorting the adjacency lists for all nodes, which is bounded by `O(E * log n)`. The main loop runs in `O(E)` time since the inner loops are constant time (at most 3*3=9). So, the total time is `O(E * log n)`. · **Space:** O(n + E) to build the initial adjacency list. The trimmed list takes O(n) space. So, the total space is O(n + E).
**Pros:** Highly efficient, with a time complexity that handles the given constraints easily.; The pre-computation step of sorting and trimming neighbors drastically reduces the search space.
**Cons:** Slightly more complex to implement due to the pre-processing step.; Requires careful reasoning to prove that considering only the top 3 neighbors is sufficient.
### Explanation
The core idea is to iterate through each edge `(u, v)` as the middle part of the sequence `a-u-v-d`. To maximize the total score, we need to pick neighbors `a` and `d` with the highest possible scores. A crucial observation is that for any optimal sequence `a*-u-v-d*`, the node `a*` must be one of the top-scoring neighbors of `u`. If `a*` wasn't, say, in the top 3, there would be at least three other neighbors of `u` with scores greater than or equal to `scores[a*]`. At most two of these could be `v` or `d*`, leaving at least one high-scoring neighbor that could replace `a*` to yield an equal or better score. The same logic applies to `d*` and `v`. Therefore, we only need to check combinations from the top 3 neighbors of `u` and `v`.

The algorithm proceeds as follows:
1. First, we build an adjacency list where for each node, we store its neighbors paired with their scores.
2. For each node, we sort its neighbors in descending order based on their scores.
3. We then trim each neighbor list to keep only the top 3. This pre-computation step is key to the efficiency.
4. We initialize `maxScore` to -1.
5. We iterate through each edge `(u, v)` in the graph.
6. For each edge, we perform a small, constant-time search. We iterate through the (at most 3) pre-computed top neighbors of `u` (let's call one `a`) and the (at most 3) top neighbors of `v` (let's call one `d`). This results in at most `3 * 3 = 9` checks per edge.
7. In each check, we ensure the four nodes `a, u, v, d` are distinct.
8. If they are, we calculate the sum of their scores and update `maxScore`.
9. Finally, we return `maxScore`.

```java
import java.util.*;

class Solution {
    public int maximumScore(int[] scores, int[][] edges) {
        int n = scores.length;
        // Store neighbors as pairs of (score, node_id)
        List<int[]>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adj[u].add(new int[]{scores[v], v});
            adj[v].add(new int[]{scores[u], u});
        }

        // Sort neighbors by score in descending order and keep top 3
        for (int i = 0; i < n; i++) {
            Collections.sort(adj[i], (a, b) -> b[0] - a[0]);
            if (adj[i].size() > 3) {
                adj[i] = adj[i].subList(0, 3);
            }
        }

        long maxScore = -1;

        // Iterate through each middle edge (u, v)
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            
            // Iterate through top neighbors of u and v
            for (int[] neighborU : adj[u]) {
                int a = neighborU[1];
                for (int[] neighborV : adj[v]) {
                    int d = neighborV[1];
                    
                    // Check for distinct nodes
                    if (a != v && d != u && a != d) {
                        long currentScore = (long) scores[u] + scores[v] + scores[a] + scores[d];
                        maxScore = Math.max(maxScore, currentScore);
                    }
                }
            }
        }

        return (int) maxScore;
    }
}
```
### Algorithm
- 1. Create an adjacency list `adj` where `adj[i]` stores pairs of `(score, neighbor_id)` for each neighbor of node `i`.
- 2. For each node `i` from `0` to `n-1`:
- 3.   Sort `adj[i]` in descending order based on scores.
- 4.   Trim `adj[i]` to keep only the top 3 neighbors.
- 5. Initialize `maxScore = -1`.
- 6. For each edge `(u, v)` in `edges`:
- 7.   For each top neighbor `a` of `u` in its trimmed list:
- 8.     For each top neighbor `d` of `v` in its trimmed list:
- 9.       If `a`, `u`, `v`, `d` are all distinct (i.e., `a != v`, `d != u`, `a != d`):
- 10.        Calculate `currentScore = scores[u] + scores[v] + scores[a] + scores[d]`.
- 11.        Update `maxScore = max(maxScore, currentScore)`.
- 12. Return `maxScore`.

# Solutions
### Java

```java
class Solution {
public
  int maximumScore(int[] scores, int[][] edges) {
    int n = scores.length;
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    for (int[] e : edges) {
      int a = e[0], b = e[1];
      g[a].add(b);
      g[b].add(a);
    }
    for (int i = 0; i < n; ++i) {
      g[i].sort((a, b)->scores[b] - scores[a]);
      g[i] = g[i].subList(0, Math.min(3, g[i].size()));
    }
    int ans = -1;
    for (int[] e : edges) {
      int a = e[0], b = e[1];
      for (int c : g[a]) {
        for (int d : g[b]) {
          if (c != b && c != d && a != d) {
            int t = scores[a] + scores[b] + scores[c] + scores[d];
            ans = Math.max(ans, t);
          }
        }
      }
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def maximumScore(self, scores: List[int], edges: List[List[int]]) -> int: g = defaultdict(list) for a, b in edges: g[a]. append(b) g[b]. append(a) for k in g . keys(): g[k] = nlargest(3, g[k], key=lambda x: scores[x]) ans = - 1 for a, b in edges: for c in g[a]: for d in g[b]: if b != c != d != a: t = scores[a] + scores[b] + scores[c] + scores[d] ans = max(ans, t) return ans

```