Maximum score reachable pair in a directed graph

You are given a directed graph where each node has an associated integer value. You may optionally perform one operation: choose two nodes i and j such that j is reachable from i, scoring val(j) - val(i). Maximize the score (the operation is optional, so the answer is at least 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.

Expected approach

• For each node i, you want the maximum val(j) over all j reachable from i (including i); the answer is max(maxReach[i] - val[i]).
• Condense the graph into strongly connected components (Tarjan/Kosaraju) to form a DAG, then DP in reverse topological order: maxReach[u] = max(value in comp(u), max over successors maxReach[child]).
• O(n + e).