这是 LeetCode 2242. 节点序列的最大得分 的详细题解。

---

题目大意

给定一个无向图，`scores[i]` 表示节点 `i` 的分数，`edges` 表示边。

求长度为 4 的节点序列的最大得分，要求：
1. 相邻节点间必须有边相连
2. 节点不能重复

如果无解，返回 `-1`。

---

核心思路

关键观察

长度为 4 的序列形如 `a - b - c - d`，其中 `(b, c)` 是中间的一条边。

要最大化得分，需要让 `a` 和 `d` 的分数尽可能高。由于 `a` 是 `b` 的邻居，`d` 是 `c` 的邻居，我们需要为每个节点保留分数最高的几个邻居。

为什么只保留 3 个邻居就够了？

考虑边 `(b, c)`，我们要找 `b` 的邻居 `a` 和 `c` 的邻居 `d`。

最坏情况：`b` 的最高邻居是 `c`，`c` 的最高邻居是 `b`（互为最大），此时需要第二高的邻居。再加上可能 `a == d` 的情况，保留 3 个 邻居足以保证找到最优解。 

算法步骤

1. 建图：用邻接表存储每个节点的邻居
2. 剪枝：每个节点只保留分数最高的 3 个 邻居
3. 枚举：遍历每条边 `(b, c)` 作为中间边，枚举 `b` 的邻居 `a` 和 `c` 的邻居 `d`
4. 去重：检查 `a, b, c, d` 是否互不相同，计算得分取最大值

---

Java 代码

```java
class Solution {
    public int maximumScore(int[] scores, int[][] edges) {
        int n = scores.length;
        
        // 建图
        List<Integer>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            graph[u].add(v);
            graph[v].add(u);
        }
        
        // 每个节点只保留分数最高的 3 个邻居
        for (int i = 0; i < n; i++) {
            Collections.sort(graph[i], (a, b) -> scores[b] - scores[a]);
            if (graph[i].size() > 3) {
                graph[i] = graph[i].subList(0, 3);
            }
        }
        
        int ans = -1;
        
        // 枚举每条边作为中间边 (b, c)
        for (int[] e : edges) {
            int b = e[0], c = e[1];
            for (int a : graph[b]) {
                for (int d : graph[c]) {
                    // 四个节点必须互不相同
                    if (a != c && a != d && b != d) {
                        int score = scores[a] + scores[b] + scores[c] + scores[d];
                        ans = Math.max(ans, score);
                    }
                }
            }
        }
        
        return ans;
    }
}
```

---

复杂度分析

项目    复杂度    
时间    `O(E)` — 建图 `O(E)`，剪枝排序 `O(n log n)`（每个节点度数有限），枚举 `O(E × 3 × 3) = O(E)`    
空间    `O(n)` — 邻接表存储    

---

关键点总结

1. 只保留 3 个最高邻居是核心剪枝，将复杂度从指数级降到线性级
2. 枚举中间边 `(b, c)` 而非枚举 4 个节点，大幅降低搜索空间
3. 去重条件 `a != c && a != d && b != d` 确保四个节点互不相同
4. 如果没有任何合法序列，`ans` 保持 `-1` 返回

> 参考：[mocowcow 题解](https://mocowcow.github.io/leetcode-2242-maximum-score-of-a-node-sequence/) 、 [CSDN 前后缀分解题单](https://blog.csdn.net/qq_43406895/article/details/133352804)