Maximum Score Reachable Pair in a Directed Graph

You are given a directed graph with val.length nodes, numbered from 0, where node i has the integer value val[i]. Each edges[k] = [u, v] is a directed edge from u to v.

Choose a pair of nodes (i, j) such that j is reachable from i by following directed edges; its score is val[j] - val[i]. Return the maximum score over all such reachable pairs. If no pair gives a positive score, you may decline to choose, so the answer is never less than 0.

Example 1

Input:  val = [1,5,3]
        edges = [[0,1],[1,2]]
Output: 4

The best pair is (0, 1): val[1] - val[0] = 5 - 1 = 4. (0, 2) scores 2 and (1, 2) scores -2.

Example 2

Input:  val = [7,2,5]
        edges = [[0,1],[1,2],[2,0]]
Output: 5

The three nodes form a cycle, so every node reaches every other. Node 1 reaches node 0 through 1 -> 2 -> 0, scoring 7 - 2 = 5. Looking only at single edges gives 3 at most.

Example 3

Input:  val = [9,4,1,10]
        edges = [[0,1],[1,2]]
Output: 0

Values only drop along the path 0 -> 1 -> 2, and node 3 can't be reached from anywhere, so no pair scores above 0.

Constraints

• 1 <= val.length <= 10^5
• -10^9 <= val[i] <= 10^9
• 0 <= edges.length <= 2 * 10^5
• edges[k] = [u, v] with 0 <= u, v < val.length
• The graph may contain cycles, self-loops and repeated edges.