簡単のため、0-indexedで考えます。

まず、目的の式を

$$\displaystyle \sum_{0\le i < j< N}\max(A_j-A_i,0) = \sum_{0\le i < j< N}\left\{ \max\left(A_j,A_i \right)-A_i\right\} = \sum_{0\le i < j< N}\max\left(A_j,A_i \right)-\sum_{0\le i < j< N}A_i$$

と式変形します。

ここで、一項目（maxの方）は全ての大きさ $2$ のインデックスの集合 $\{i,j\}$ に対する $\displaystyle \max\left(A_i,A_j\right)$ の総和と捉えられるので、この総和は $A$ の順番によらないことがわかります。これにより、 $A$ を昇順にソートしたものを $B$ とおくと、

$$\begin{aligned} &\phantom{=} \sum_{0\le i < j< N} \max\left(A_j,A_i \right)\\ &= \sum_{0\le i < j< N} \max\left(B_j,B_i \right)\\ &=\sum_{0\le i < j< N} B_j\\ &=\sum_{j=0}^{N-1} jB_j \end{aligned}$$

として求めることができます。

一方、二項目（$A_i$ の方）も同様に式変形をすると、

$$\sum_{0\le i < j< N} A_i=\sum_{i=0}^{N-1} (N-1-i)A_i$$

となるので、最終的に求める値は

$$\sum_{i=0}^{N-1} iB_i -\sum_{i=0}^{N-1} (N-1-i)A_i$$

と表すことができます。この値は配列のソートを用いることで簡単に求めることができます。

以上でこの問題が解けました。計算量はソートがボトルネックとなり $O(N\log N)$ となります。

実装例(Python3)

N = int(input())
A = list(map(int, input().split()))
B = sorted(A)
ans = 0
for i in range(N):
  ans += i * B[i]
  ans -= (N - 1 - i) * A[i]
print(ans)

N = int(input())
A = list(map(int, input().split()))
B = sorted(A)
ans = 0
for i in range(N):
  ans += i * B[i]
  ans -= (N - 1 - i) * A[i]
print(ans)