n towns numbered 0 to n − 1. Town i is worth values[i] points. Two-way roads are given in roads: the pair [a, b] means a road between towns a and b.
A route is a sequence of **four different** towns in which every two neighbouring towns are joined by a road. Its value is the sum of the points of those four towns.
Return the largest value of a route, or -1 if there is no route at all.values=[3, 10, 1, 7, 6], roads=[[0, 1], [1, 2], [2, 3], [1, 3], [3, 4]] → 26
The route 0 → 1 → 3 → 4 uses roads 0–1, 1–3 and 3–4 and collects 3 + 10 + 7 + 6 = 26. Town 2 (worth 1) is not worth visiting.
values=[5, 5, 5, 5, 5], roads=[[0, 1], [0, 2], [0, 3], [0, 4]] → -1
Every road leaves town 0. From any other town you can only go back to 0, which is not allowed, so no four-town route exists: -1.
values=[2, 4, 6, 8], roads=[[0, 1], [1, 2], [2, 3]] → 20
The only route is along the chain 0 → 1 → 2 → 3 (or backwards): 2 + 4 + 6 + 8 = 20.
n = values.length ≤ 5 · 10⁴values[i] ≤ 10⁸roads.length ≤ 5 · 10⁴roads[i] = [a, b], 0 ≤ a, b ≤ n − 1, a ≠ bvalues=[3, 10, 1, 7, 6], roads=[[0, 1], [1, 2], [2, 3], [1, 3], [3, 4]]
26
Run checks the first 3 tests in your browser. Submit checks all 69 tests on the server, hidden ones included.