2242

2242. Maximum Score of a Node Sequence (Hard)

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:

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:

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.

Companies: Google

Related Topics:
Array, Graph, Sorting, Enumeration

Similar Questions:

• Get the Maximum Score (Hard)

Solution 1.

len = 1 => Find the max score node len = 2 => Try each edge. O(E) Time. len = 4 => Try each edge. For each edge, for the two nodes, try their top 3 neighbor nodes. This takes O(N + E * 3 * 3) = O(N + E) time.

Precomputing the top 3 neighbor nodes of all nodes takes O(E) time because each edge is used twice.

// OJ: https://leetcode.com/problems/maximum-score-of-a-node-sequence
// Author: github.com/lzl124631x
// Time: O(N + E)
// Space: O(N + E)
class Solution {
public:
    int maximumScore(vector<int>& S, vector<vector<int>>& E) {
        int N = S.size(), ans = -1;
        vector<vector<int>> G(N);
        for (auto &e : E) {
            int u = e[0], v = e[1];
            G[u].push_back(v);
            G[v].push_back(u);
        }
        vector<array<int, 3>> top(N, {-1,-1,-1});
        for (int u = 0; u < N; ++u) {
            auto &t = top[u];
            for (int v : G[u]) {
                if (t[0] == -1 || S[v] > S[t[0]]) t[2] = t[1], t[1] = t[0], t[0] = v;
                else if (t[1] == -1 || S[v] > S[t[1]]) t[2] = t[1], t[1] = v;
                else if (t[2] == -1 || S[v] > S[t[2]]) t[2] = v;
            }
        }
        for (auto &e : E) {
            int u = e[0], v = e[1];
            for (int i = 0; i < 3; ++i) {
                int nu = top[u][i];
                if (nu == -1) break;
                if (nu == v) continue;
                for (int j = 0; j < 3; ++j) {
                    int nv = top[v][j];
                    if (nv == -1) break;
                    if (nv == u || nv == nu) continue;
                    ans = max(ans, S[u] + S[v] + S[nu] + S[nv]);
                }
            }
        }
        return ans;
    }
};