Solution 1

Due to the constraints \(X_i < Y_i\), this graph is a DAG (Directed Acyclic Graph, direct graph without a cycle).
On this DAG, consider the following DP (Dynamic Programming):

\(\mathrm{dp}[i]\) : The cheapest price of gold in the towns that is reachable from town \(i\) (except for town \(i\) itself)

In the increasing order of \(i\), for each town \(j\) that can be directly traveled from \(i\), calculate \(\mathrm{dp}[j] \leftarrow \min(\mathrm{dp}[j], \mathrm{dp}[i], A_i)\) to calculate entire DP.

Once we obtained this, the answer is the maximum of \(A_i - \mathrm{dp}[i]\). The total time complexity is \(O(N + M)\).

Solution 2

First, take the town \(x_1\) with the lowest gold price. Perform breadth-first search to enumerate every town \(y\) that is reachable from \(x_1\), and record the profit when buying in town \(x_1\) and selling in town \(y\)
Do the same thing for town \(x_2\) with the second lowest gold price; but this time, we don’t have to consider the town \(y\) that is reachable from town \(x_1\). (This is because it is always better to buy in town \(x_2\) and sell in town \(y\) than to buy in town \(x_1\) and sell in town \(y\))
Therefore, during the breadth-first search, we do not have to push the town that has already been inspected.

Repeat it in the increasing order of gold price, and the optimal solution is one of the recorded profits.
Since we don’t push the vertices that has been already seen, the overall time complexity is \(O(N \log(N) + M)\).

(Advanced) Without constraints \(X_i < Y_i\)

That is, what if the given graph is not a DAG but a general directed graph?
Since Solution 2 does not use this constraints, it can be applied in the same way.
Also, after decomposing into strongly connected components, Solution 1 can also be applied.