この問題を分割統治法を適用して解きます。

\(\sum_{1 \le i < j \le N} \max(A_j-A_i,0)= \sum_{1 \le i < j \le M} \max(A_j-A_i,0) + \sum_{M+1 \le i < j \le N} \max(A_j-A_i,0) + \sum_{1 \le i \le M < j \le N} \max(A_j-A_i,0)\) と分解して、始めの \(2\) 項を再帰で処理します。最後の \(1\) 項は \(i,j\) が独立に動かせるのでソートと尺取り法を用いることで \(\mathrm{O}(N \log N)\) で処理可能です。

\(M = \frac{N}{2}\) とすることを繰り返すことで、全体で \(\mathrm{O}(N \log^2 N)\) でこの問題を解くことが出来ます。

実装例