Let's now consider the maximum scalar product.
In this case, we're given two sequences of integers of the same lengths namely,
the sequence a of lengths n and the sequence b of
lengths n. What we would like to do is to find the permutation
of the second sequence so that
the scalar product of a with this permutation is as large as possible.
So the scalar product of sequences a0,
a1 and so on,
a and minus one and the sequence c0 of c1 and so on,
cn minus one is defined as just the sum of products a0c0,
a1c1, and so on,
an minus one, cn minus one.
So put it otherwise,
what we would like to do is to pair each element of a with each element of
b with an element of b such that the sum of the product of pairs is as large as possible.
For example, if we're given two sequences two,
three, nine and seven, four,
two, then the optimum numbers that we can get in this case is equal to 79.
This can be revealed by the following as scalar product,
so we pair two,
the element of the first sequence with two,
the element of the second sequence,
then paired with the element three with the element four and finally,
the element seven with the element nine,
I'm sorry it was the element seven, okay?
So the result is 79 and we will soon find the way of finding these particular solution.
So the greediest strategy in this case is again quite natural.
So, the idea is to pair
the largest element of the sequence a with the largest element of the sequence b.
So if we prove that this is
indeed leads to an optimum solutions then we can do the following,
select just optimum, the maximum value of a,
select the maximum value of b, pair them,
remove them from a and b and repeat, okay?
Now, let's prove that all this exists.
The solution where the maximum element of a,
we denote it by ai,
is paired with the maximum element of b,
we denote it by bj.
Okay, so for this consider some optimum solution, okay?
So first of all if it pairs ai and bj and then we are done.
So we know that the existing optimal solution which pairs these two particular numbers.
So now, assume that it pairs ai with some different element of b.
So assume that S looks as follows.
It is ai times bp,
plus aq times bj.
So ai is paired with bp and aq is paired with bj.
What we need to prove is that there still exists some other optimum solution,
which paired ai with bj.
So when there is a natural tweek in this case,
let's just swap these two pairs.
So instead of fast let's consider a solution as prime,
which looks almost the same as S with the only difference instead of using aibp and aqbj,
it uses the following two pairs aibj and aqbp.
So again, we just swap these two pairs instead of pairing these two guys,
we pair with this two guys.
Okay, so what we need to show now is that S prime is not worse than
S. And for this we just subtract the value of S from the value of S prime.
So since these two solutions are almost the
same what is left are only these four products.
So it is aibj plus aqbp,
minus aibp, minus aqbj.
Then it is not difficult to see that it can be rewritten as follows.
It is equal to ai minus aq,
times bj minus bp,
and this is in turn non-negative for a simple reason.
So we know that ai is the largest element of i,
of a, I'm sorry,
which means that ai is at least take aq
just for exactly the same reason bj is the largest number of b,
so which means that bj is greater than bp is at least bp.
So this is a product of two non-negative numbers,
which is so this is non-negative which
finally proves that these give as an optimum solution,
which pairs ai and bj, okay?
So then what remains to be done is to convert that
into an algorithm and we will discuss the algorithm actually.
So what you see here is a simple Python code,
so we first check whether the lengths of the given two sequences A and B are equal,
we then declare the variable which initialize it with zero.
And then while the lengths of A is,
while the rest sum remaining elements in A,
we repeat the following step.
We find two maximum elements in A and B,
we denoted by am and bm.
Then we add their product to the result and
then we remove these two elements from a and b.
Finally, when there are no elements left in a re return the result, okay?
So the running time of this algorithm is what I think
is that bigger often square for simple reasons.
So, at most, there are exactly n iterations of the while loop and inside
every iteration what we need to do is to find
two maximum section and to remove two elements.
And all the separations can be done just by
simple linear scan in a linear amount of work.
