---
# System prepended metadata

title: 2242. Maximum Score of a Node Sequence
tags: [Leetcode, Hard, Greedy]

---

# 2242. Maximum Score of a Node Sequence
###### tags: `Leetcode` `Hard` `Greedy`
Link: https://leetcode.com/problems/maximum-score-of-a-node-sequence/
## 思路 $O(N+M)$ $O(N+M)$
思路参考[这里](https://leetcode.com/problems/maximum-score-of-a-node-sequence/discuss/1953706/JavaPython-Keep-3-Biggest-Neighbours)
1. 先把每条边的两个点拿出来 找到他们邻居当中score最大的三个 三个是因为它不能跟这条边的另一个点和另一个点的邻居重复
2. 然后遍历每条边和priority queue里面的所有邻居 更新答案
## Code
```java=
class Solution {
    public int maximumScore(int[] scores, int[][] edges) {
        Queue<Integer>[] pq = new PriorityQueue[scores.length];
        for(int i=0; i<scores.length; i++){
            pq[i] = new PriorityQueue<>((a,b)->(scores[a]-scores[b]));
        }
        for(int[] edge:edges){
            pq[edge[0]].add(edge[1]);
            pq[edge[1]].add(edge[0]);
            if(pq[edge[0]].size()>3) pq[edge[0]].poll();
            if(pq[edge[1]].size()>3) pq[edge[1]].poll();
        }
        int ans = 0;
        for(int[] edge:edges){
            for (int i : pq[edge[0]]){
                for (int j : pq[edge[1]]){
                    if (i!=j && i!=edge[1] && j!=edge[0]){
                        ans = Math.max(ans, scores[i]+scores[j]+scores[edge[0]]+scores[edge[1]]);
                    }
                }
            }
        }
        
        return ans==0?-1:ans;
    }
}
```