Maximum sum difference between two sorted array elements under one condition We're given two arrays $A$ and $B$ with size $N$ and $M$ respectively. We want to find a set $P = \{(a_1, b_1), \dots, (a_s,b_s)\}$ such that


for each $i\in\{1, \dots, s\}$, $a_i\in A$, $b_i\in B$ and $a_i&gt;b_i$ and $a_i,b_i$ musn't be chosen before;
$\sum_{i=1}^s (a_i-b_i)$ is maximized.


A natural approach is to sort array $A$ in descending order and $B$ in ascending order, initialize $i$ and $j$ to $1$, then iterate: while $A[i] &gt; B[j]$ add $A[i] - B[j]$. How we can prove that this solution works?
Two sets A and B.  Using i and j only once maximize the ∑(a[i] - b[j]).  Not required to use and i and j.

I don't know if this is a hard proof but  

For $A[i] &gt; B[j]$
∑(a[i]−b[i])  =  ∑(a[i]) - ∑(b[i])

So the problem is reduced to maximize $A[i] &gt; B[j]$
Reverse sorting maximizes the number of $A[i] &gt; B[j]$  

Or another way to say it
maximizes ∑(a[i]) and minimizes ∑(b[i])
Descending sorting maximizes ∑(a[i])
Ascending  sorting minimizes ∑(b[i])