Maximum score reachable pair in a directed graph

Problem You are given a directed graph where each node has an associated integer value. Choose a pair of nodes (i, j) such that j is reachable from i by following directed edges, and score 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.

Input / Output

• Input: node values val[] and directed edges [u, v].
• Output: the maximum achievable val(j) - val(i) over all reachable pairs (i, j), or 0 if no positive pair exists.

Constraints

• 1 <= n <= 10^5, edges up to ~2 * 10^5.
• Node values may be negative.
• The graph may contain cycles.

Example

• Values [1, 5, 3] with edges 0->1, 1->2: best is val(1) - val(0) = 4.