解法 1

\(X_i < Y_i\) という制約のため、このグラフは DAG (Directed Acyclic Graph, 閉路を含まない有向グラフ) です。
この DAG 上で以下のような DP (動的計画法) を考えます。

\(\mathrm{dp}[i]\) : 街 \(i\) に到達できる街 (街 \(i\) 自身を含まない) における金の最安値

\(i\) の昇順に、\(i\) から直接移動できる各街 \(j\) について、\(\mathrm{dp}[j] \leftarrow \min(\mathrm{dp}[j], \mathrm{dp}[i], A_i)\) とすればこの DP は計算できます。

これが計算できれば、\(A_i - \mathrm{dp}[i]\) の最大値が答えとなります。
計算量は \(O(N + M)\) です。

解法 2

まず、金の取引価格が一番低い街を一つとって街 \(x_1\) とします。幅優先探索で、街 \(x_1\) から辿りつける街 \(y\) を列挙し、街 \(x_1\) で買い街 \(y\) で売った 場合の利益を記録しておきます。
街 \(x_1\) の次に金の取引価格が低い街 \(x_2\) についても同様のことをしますが、このとき街 \(x_1\) から到達できる街 \(y\) は考えなくてよいです。(街 \(x_2\) で買って街 \(y\) で売るくらいなら街 \(x_1\) で買って街 \(y\) で売っても損をしないため)
そのため、幅優先探索の過程で既に見た頂点は push しないことにしてよいです。

更にこれを、金の取引価格が小さい順に繰り返すと、記録した利益の中に最適解があります。
既に見た頂点は push しないことにしたので、全体の計算量はソートを含めて \(O(N \log(N) + M)\) で済みます。

(発展) \(X_i < Y_i\) の制約がない場合

つまり、与えられるグラフが DAG とは限らず一般の有向グラフである場合です。
解法2はこの制約を利用していないのでそのまま適用できます。
また、強連結成分分解をすることで解法1を適用することもできます。