Solution:
Due to the fact that our graph can have cycles, this complicates things for us. Let's build a new graph in which we "compress" all the components of a strong connection into a single vertex, so new graph will be acyclic. During this process let's memorize maximum(maximumWeight[v]) and minimum(minimumWeigh[v]) weights of the edges for each strongly connected components.
We spent O(|V| + |E|) time for it, where |V| is count of vertexes and |E| is count if edges.
After that let's make a topological sorting of given graph in O(|V|+|E|) time complexity. Then let's calculate simple DP.
dpMax[v] - the maximum weight of the edge to which there is a path from this vertex.
dpMin[v] - the minimum weight of the edge to which there is a path from this vertex.
Default value:
If vertex v is strongly connected component, then maximum and minimum weights already calculates in maximumWeight[v] and minimumWeigh[v], so dpMax[v] = maximumWeight[v] and dpMin[v] = minimumWeight[v].
Otherwise maximumWeight[v] = -Infinity and minimumWeigh[v] = Infinity.
In topological order let's improve our DP for each vertex:
int answer = -Infinity;
for(auto v : vertexesInTopologicalOrder) {
int newMinDp = dpMin[v], newMaxDp = dpMax[v];
for(auto e : v.outgoingEdges) {
int l = dpMin[v];
int r = dpMax[v];
l = min(l, e.weight);
r = max(r, e.weight);
l = min(l, dpMin[e.target]);
r = max(r, dpMax[e.target]);
answer = max(answer, e.weight - l);
answer = max(answer, r - e.weight);
newMinDp = min(newMinDp, l);
newMaxDp = max(newMaxDp, r);
}
dpMin[v] = newMinDp;
dpMax[v] = newMaxDp;
}
Since we calculating DP in topological order, the DP at achievable vertexes have already been calculated.
For a better understanding, let's look at an example.
Let's say we have such an initial graph.
After compression, the graph will look something like this.
After topological sorting, we get this order of vertices. (Green numbers)
Sequentially calculate all DP values, along with updating the answer.
Final answer 6 will be achieved during calculating top vertex DP.
I hope it turned out to be quite detailed and clear. Final time complexity is O(|V|+|E|).
