lc2242. 节点序列的最大得分（枚举）

给你一个 n 个节点的 无向图 ，节点编号为 0 到 n - 1 。

给你一个下标从 0 开始的整数数组 scores ，其中 scores[i] 是第 i 个节点的分数。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] ，表示节点 ai 和 bi 之间有一条 无向 边。

一个合法的节点序列如果满足以下条件，我们称它是 合法的 ：

序列中每 相邻 节点之间有边相连。
序列中没有节点出现超过一次。
节点序列的分数定义为序列中节点分数之 和 。

请你返回一个长度为 4 的合法节点序列的最大分数。如果不存在这样的序列，请你返回 -1 。

示例 1：

输入：scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
输出：24
解释：上图为输入的图，节点序列为 [0,1,2,3] 。
节点序列的分数为 5 + 2 + 9 + 8 = 24 。
观察可知，没有其他节点序列得分和超过 24 。
注意节点序列 [3,1,2,0] 和 [1,0,2,3] 也是合法的，且分数为 24 。
序列 [0,3,2,4] 不是合法的，因为没有边连接节点 0 和 3 。
示例 2：

输入：scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]]
输出：-1
解释：上图为输入的图。
没有长度为 4 的合法序列，所以我们返回 -1 。

提示：

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
不会有重边。

class Solution {
    /**
    设序列为 a-x-y-b（− 表示边），枚举 {edges} 中的每条边，作为序列正中间的那条边，即 x−y。
    我们需要把与 x 相邻的点中，分数最大且不同于 y 和 b 的点作为 a；把与 y 相邻的点中，分数最大且不同于 x 和 a 的点作为 b。
    只需要取最大的三个就可以
     */
    public int maximumScore(int[] scores, int[][] edges) {
        int n = scores.length;
        List<int[]>[] g = new ArrayList[n];
        for (int i = 0; i < n; ++i) g[i] = new ArrayList<>();
        for (int[] edge : edges) {
            int a = edge[0], b = edge[1];
            g[a].add(new int[]{b, scores[b]});
            g[b].add(new int[]{a, scores[a]});
        }
        //只需要保留前三个点
        for (int i = 0; i < n; ++i) {
            if (g[i].size() > 3) {
                g[i].sort((a, b) -> b[1] - a[1]);
                g[i] = new ArrayList<>(g[i].subList(0, 3));
            }
        }
        int res = -1;
        //枚举边
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            for (int[] tem1 : g[x]) {
                int a = tem1[0];
                for (int[] tem2 : g[y]) {
                    int b = tem2[0];
                    if (a != y && b != x && a != b) {
                        res = Math.max(res, scores[a] + scores[b] + scores[x] + scores[y]);
                    }
                } 
            }
        }
        return res;
    }
}