I have two arrays, namely $a$ and $b$. Both have the same length $n$. I have to find the maximum value of $\sum a_i b_j$, in which every element can be used at most one time. My algorithm for solving this problem is:
- Sort both $a$ and $b$ in non increasing order.
- Pick the values from the array in order of greatest to smallest. Calculate their product and add them to sum.
On the arrays $a = \{2,3,4\}$ and $b = \{4,5,6\}$, the algorithm runs as follows:
- Firstly, sorting the arrays: $a = \{4,3,2\}$ and $b = \{6,5,4\}$.
Then picking values from the first to last, gives the answer $(4\cdot6) + (3\cdot5) + (2\cdot4) = 24 + 15 + 8 = 47$.
Here what I have used is a greedy algorithm. How to prove its correctness? What I want to know is, how to prove that this algorithm always gives the maximum answer?