2242. Maximum Score of a Node Sequence Hard

1/**
2 * [2242] Maximum Score of a Node Sequence
3 *
4 * There is an undirected graph with n nodes, numbered from 0 to n - 1.
5 * 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.
6 * A node sequence is valid if it meets the following conditions:
7 *
8 * There is an edge connecting every pair of adjacent nodes in the sequence.
9 * No node appears more than once in the sequence.
10 *
11 * The score of a node sequence is defined as the sum of the scores of the nodes in the sequence.
12 * Return the maximum score of a valid node sequence with a length of 4. If no such sequence exists, return -1.
13 *  
14 * Example 1:
15 * <img alt="" src="https://assets.leetcode.com/uploads/2022/04/15/ex1new3.png" style="width: 290px; height: 215px;" />
16 * Input: scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
17 * Output: 24
18 * Explanation: The figure above shows the graph and the chosen node sequence [0,1,2,3].
19 * The score of the node sequence is 5 + 2 + 9 + 8 = 24.
20 * It can be shown that no other node sequence has a score of more than 24.
21 * Note that the sequences [3,1,2,0] and [1,0,2,3] are also valid and have a score of 24.
22 * The sequence [0,3,2,4] is not valid since no edge connects nodes 0 and 3.
23 *
24 * Example 2:
25 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/17/ex2.png" style="width: 333px; height: 151px;" />
26 * Input: scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]]
27 * Output: -1
28 * Explanation: The figure above shows the graph.
29 * There are no valid node sequences of length 4, so we return -1.
30 *
31 *  
32 * Constraints:
33 *
34 * n == scores.length
35 * 4 <= n <= 5 * 10^4
36 * 1 <= scores[i] <= 10^8
37 * 0 <= edges.length <= 5 * 10^4
38 * edges[i].length == 2
39 * 0 <= ai, bi <= n - 1
40 * ai != bi
41 * There are no duplicate edges.
42 *
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/maximum-score-of-a-node-sequence/
47// discuss: https://leetcode.com/problems/maximum-score-of-a-node-sequence/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50use std::cmp;
51impl Solution {
52    pub fn maximum_score(scores: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
53        let mut max_neighbour = vec![(-1, -1, -1); scores.len()];
54        for e in &edges {
55            Self::insert(&mut max_neighbour, e[0] as usize, e[1] as usize, &scores);
56            Self::insert(&mut max_neighbour, e[1] as usize, e[0] as usize, &scores);
57        }
58
59        let mut max = -1;
60        for e in &edges {
61            let x = e[0] as usize;
62            let y = e[1] as usize;
63            let current = scores[x] + scores[y];
64            for i in [max_neighbour[x].0, max_neighbour[x].1, max_neighbour[x].2] {
65                if i == -1 || i as usize == y {
66                    continue;
67                }
68
69                for j in [max_neighbour[y].0, max_neighbour[y].1, max_neighbour[y].2] {
70                    if j == -1 || j as usize == x || i == j {
71                        continue;
72                    }
73                    max = cmp::max(max, current + scores[i as usize] + scores[j as usize]);
74                }
75            }
76        }
77
78        max
79    }
80
81    fn insert(
82        max_neighbour: &mut Vec<(i32, i32, i32)>,
83        n: usize,
84        target: usize,
85        scores: &Vec<i32>,
86    ) {
87        if max_neighbour[n].0 == -1 {
88            max_neighbour[n].0 = target as i32;
89        } else if max_neighbour[n].1 == -1 {
90            if scores[target] > scores[max_neighbour[n].0 as usize] {
91                max_neighbour[n].1 = max_neighbour[n].0;
92                max_neighbour[n].0 = target as i32;
93            } else {
94                max_neighbour[n].1 = target as i32;
95            }
96        } else if max_neighbour[n].2 == -1 {
97            if scores[target] > scores[max_neighbour[n].0 as usize] {
98                max_neighbour[n].2 = max_neighbour[n].1;
99                max_neighbour[n].1 = max_neighbour[n].0;
100                max_neighbour[n].0 = target as i32;
101            } else if scores[target] > scores[max_neighbour[n].1 as usize] {
102                max_neighbour[n].2 = max_neighbour[n].1;
103                max_neighbour[n].1 = target as i32;
104            } else {
105                max_neighbour[n].2 = target as i32;
106            }
107        } else {
108            if scores[target] > scores[max_neighbour[n].0 as usize] {
109                max_neighbour[n].2 = max_neighbour[n].1;
110                max_neighbour[n].1 = max_neighbour[n].0;
111                max_neighbour[n].0 = target as i32;
112            } else if scores[target] > scores[max_neighbour[n].1 as usize] {
113                max_neighbour[n].2 = max_neighbour[n].1;
114                max_neighbour[n].1 = target as i32;
115            } else if scores[target] > scores[max_neighbour[n].2 as usize] {
116                max_neighbour[n].2 = target as i32;
117            }
118        }
119    }
120}
121
122// submission codes end
123
124#[cfg(test)]
125mod tests {
126    use super::*;
127
128    #[test]
129    fn test_2242() {
130        assert_eq!(
131            Solution::maximum_score(
132                vec![9, 20, 6, 4, 11, 12],
133                vec![vec![0, 3], vec![5, 3], vec![2, 4], vec![1, 3]]
134            ),
135            -1
136        );
137        assert_eq!(
138            Solution::maximum_score(
139                vec![5, 2, 9, 8, 4],
140                vec![
141                    vec![0, 1],
142                    vec![1, 2],
143                    vec![2, 3],
144                    vec![0, 2],
145                    vec![1, 3],
146                    vec![2, 4]
147                ]
148            ),
149            24
150        );
151    }
152}
153