# Thread: Finding the biggest sum in a set

1. ## Finding the biggest sum in a set

Hi, I'm trying to create an algorithm, and I'm stuck at one point. Say I have a set of N items, all have their points, and ordered by their ranks.
For example:
list1 = { // N = 4
1: (item1, points: 100, rank:1),
2: (item2, points:55, rank:2),
3: (item3, points:55, rank:2),
4: (item4, points:45, rank:3) }
and so on.

list2 is another list of these 4 (N) items, but with different points, thus different ranks. I'm trying to do a comparison for these two lists, like the sum of the differences of item ranks in two lists.For example:

list2 = {
1: (item4, points: 10, rank:1),
2: (item3, points:9, rank:2),
3: (item2, points:8, rank:3),
4: (item1, points:7, rank:4) }

in this case the sum of differences S = (item1 rank difference + item2 " " + ....) S= 3 + 1 + 0 + 2 = 6
in order to compare it with the worst case, I need this sum's worst value for different N's.
so, what is the maximum value of S in terms of N? S_max (N) =?
Thanks for any help.

- Notes:
My solution was assuming the two lists were reversely-ordered for the worst-case sum. Which yielded this solution:
if (N is even)
Smax=(N^2)/4 ;
else (N is odd)
Smax =((N^2)-1)/4 ;

But this solution seems to be wrong, since sometimes it yields negativepercent similarity, which means the current sum (S) is greater than Smax.

2. ## Re: Finding the biggest sum in a set

Just so I understand the problem, shouldn't your two lists make S = 3 + 1 + 1 + 3 = 8?
item 1: positions 1 and 4 difference = 3
item 2: positions 2 and 3 difference = 1
item 3: positions 3 and 2 difference = 1
item 4: positions 4 and 1 difference = 3

If I've understood, then my guess is that this inversion is the worst case, but I haven't thought about how to prove it.

Is this the correct statement of your problem (Sym(A) is the set of bijections from A onto itself)?

Let $A = \{1, 2, ..., N\}$. For $f, g \in Sym(A)$, define $\Delta(f, g) = \Sigma_{a \in A} |f(a)-g(a)|$.

Find the upper bound of $\Delta$ as a function of $N = |A|$.

----

The one thing I can see quickly is that to exploit that the sum over a set, that includes a bijection of that set, can be permuted to order things in a simplier way. This is exploiting that addition is commutative and that you're summing over everything in the set. When you do that, the order in which you do the summing doesn't matter - you can permute it however you like.

$\Delta(f, g) = \Sigma_{a \in A} |f(a)-g(a)| = \Sigma_{a = 1}^N |f(a)-g(a)| = \Sigma_{b = 1}^N |f(g^{-1}(b))-b|$ using, generically, $a = g^{-1}(b)$.

Note that's saying that $\Delta(f, g) = \Delta(f \circ g^{-1}, identity)$.

This simplfies the the problem to looking for just one function, not two.

The problem becomes: Find the $f \in Sym(A)$ that maximizes $\Sigma_{k = 1}^N |f(k)-k|$.

And, yeah, I bet f(k) = N+1 - k gives the maximum for that sum. With that f, the sum becomes:

$\Sigma_{k = 1}^N |f(k)-k| = \Sigma_{k = 1}^N |(N+1 - k) - k| = \Sigma_{k = 1}^N |N+1 - 2k|$

$= \Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} |N+1 - 2k| + \Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N |N+1 - 2k|$

$= \Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} (N+1 - 2k) + \Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N (2k - N- 1)$

$= \Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} (N+1) - 2\Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} k + 2\Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N k - \Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N (N+1)$

$= \left(\Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} (N+1) - \Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N (N+1) \right) + 2 \left( - \Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} k + \Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N k \right)$.

Looking at just the k sums:

$- \Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} k + \Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N k$

$= -\Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} k + \left( -\Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} k + \Sigma_{k = 1}^N k \right)$

$= -2\Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} k + \Sigma_{k = 1}^N k$

$= -2q(\lfloor \frac{N+1}{2}\rfloor) + q(N)$, where $q(n) = \frac{n(n+1)}{2}$.

Looking at just the constant sums:

$\Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} (N+1) - \Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N (N+1) \right}$

$= (N+1) \left( \Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} 1 - \Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N 1 \right)$

$= (N+1) \left( \lfloor \frac{N+1}{2} \rfloor - (N + 1 - (1 + \lfloor \frac{N+1}{2} \rfloor) \right)$

$= (N+1) \left( 2\lfloor \frac{N+1}{2} \rfloor - N \right)$.

Thus when f(k) = N+1 - k, have:

$\Sigma_{k = 1}^N |f(k)-k| = (N+1) \left( 2\lfloor \frac{N+1}{2} \rfloor - N \right) + 2 \left( -2q(\lfloor \frac{N+1}{2} \rfloor + q(N) \right)$,

where $q(n) = \frac{n(n+1)}{2}$.

Note that $\left( 2\lfloor \frac{N+1}{2} \rfloor - N \right) = 1$ when $N$ is odd, and $0$ when $N$ is even.

If N even, then $\lfloor \frac{N+1}{2} \rfloor = N/2$, and so

$q(\lfloor \frac{N+1}{2} \rfloor ) = q(N/2) = (N/2)((N/2)+1)/2 = N(N+2)/8$, so

$\Sigma_{k = 1}^N |f(k)-k| = (N+1)(0) + 2 \left( -2( \frac{N(N+2)}{8} ) + ( \frac{N(N+1)}{2} ) \right)$

$= -\frac{N(N+2)}{2} + \frac{2N(N+1)}{2}$

$= (\frac{N}{2}) ( -(N+2) + 2(N+1) ) = (\frac{N}{2}) ( N ) = \frac{N^2}{2}$.

If N odd, $\lfloor \frac{N+1}{2} \rfloor = (N+1)/2$, and so

$q(\lfloor \frac{N+1}{2} \rfloor ) = q((N+1)/2)$

$= ((N+1)/2)((N+1)/2)+1)/2 = (N+1)(N+3)/8$, so

$\Sigma_{k = 1}^N |f(k)-k| = (N+1)(1) + 2 \left( -2( \frac{(N+1)(N+3)}{8} ) + ( \frac{N(N+1)}{2} ) \right)$

$= N+1 + \left( -\frac{(N+1)(N+3)}{2} + \frac{2N(N+1)}{2} \right)$

$= N+1 + \frac{(N+1)}{2}( -(N+3) + 2N )= N+1 + \frac{(N+1)}{2}( N-3 )$

$= (N+1) (1 + \frac{N-3}{2}) = (N+1) \frac{N-1}{2} = \frac{N^2-1}{2}$.

Thus the $S$ = $\Delta(f, identity)$ for that $f$ is $\frac{N^2}{2}$ when N is even, and $\frac{N^2-1}{2}$ when N is odd.