Use Dijkstra’s algorithm, but instead of adding up edge weights, when prospecting an edge \(u \rarr v\) (assuming \(A_u \le A_v\)), update node \(v\) with the cost represented by the tuple \((A_v, -s)\), where \(s\) is the number of unique values on the path (the score you are trying to maximize).

This works because whenever you prospect an edge \(u \rarr v\), the prospective cost of \(v\) is never lower than the cost of \(u\). (\(s\) only ever increases if \(A_v\) does also)

Note that since we only prospect edges where \(A_u \le A_v\), we might never reach node \(N\), in which case the answer is \(0\).

The problem is thus solved in \(O((N+M) \log N)\).

Alternatively, this problem can be viewed as Dijkstra’s on a directed graph where edge \(u \rarr v\) has cost \(0\) if \(A_u = A_v\), or cost \((A_v - A_u) \omega - 1\) if \(A_u < A_v\) (where \(\omega\) is a sufficiently large value, that numbers of the form \(a \omega + b\) compare like tuples \((a, b)\))