2242. Maximum Score of a Node Sequence

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.

class Solution {
public:
    int maximumScore(vector<int>& scores, vector<vector<int>>& edges) {
        int res = -1, n = scores.size();
        vector<vector<int>> adj(n);
        for(auto& e : edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }
        for(auto& a : adj) {
            partial_sort(begin(a), begin(a) + min(a.size(), 3ul), end(a), [&](int u, int v) {return scores[u] > scores[v];});
            a.resize(min(a.size(), 3ul));
        }
        for(auto& e: edges) {
            for(auto& u : adj[e[0]])
                for(auto& v : adj[e[1]])
                    if(u != e[1] and v != e[0] and u != v)
                        res = max(res, scores[u] + scores[v] + scores[e[0]] + scores[e[1]]);
        }
        
        return res;
    }
};