# Maximum possible sum of index differences of two lists

I have two ordered lists, $$l_1$$ and $$l_2$$, each containing $$N$$ elements $${e_1, e_2, ..., e_N }$$ (each only once) in some order.

For each of these elements I calculate their absolute index difference between those two lists and sum them up.

Example with $$N=3$$:

$$l_1 = [e_1, e_2, e_3]$$

$$l_2 = [e_2, e_3, e_1]$$

$$d_{e_1} = abs(l_1.index(e1) - l_2.index(e1)) = abs(1 - 3) = 2$$

$$d_{e_2} = abs(l_1.index(e2) - l_2.index(e2)) = abs(2 - 1) = 1$$

$$d_{e_3} = abs(l_1.index(e3) - l_2.index(e3)) = abs(3 - 2) = 1$$

$$result = d_{e_1} + d_{e_2} + d_{e_3} = 2 + 1 + 1 = 4$$

What is the maximum possible sum of differences for $$N$$ elements?

If the two lists have their elements in the same order the sum of differences is the minimum, 0.

The distributions look like this:

It may be that the answer is $$\lfloor N^2/2 \rfloor$$, achieved by letting $$l_2$$ have the reverse order of $$l_1$$, so there would only be one permutation which has the maximum difference, but I'm not certain

• When you say $e_1, \ldots, e_N$ do you mean $1, \ldots, N$? Otherwise hard to bound the difference, consider $1, N, N^2, \ldots, N^N$ as your list in straight and reverse order... Commented Jul 28, 2023 at 14:03
• Yes, the integers work
– 2080
Commented Jul 28, 2023 at 14:10
• @gt6989b The elements' values do not matter; OP is taking the difference of each element's positions in the two permutations. Commented Jul 28, 2023 at 16:01
• @angryavian missed that; in that case, just taking a rearranged order of integers $1,\ldots,N$ is sufficient. It is intuitively obvious that the greedy solution produces the optimal answer. I tried this in Excel for a couple and this answer can be duplicated but cannot be beat. The max sum abs-diffs I found for $N=1,2,3,4,5$ are $0,2,4,8,12$ Commented Jul 28, 2023 at 16:15
• @angryavian Aye, it seems to be this OEIS sequence: oeis.org/…
– 2080
Commented Jul 28, 2023 at 16:33

We can without loss of generality assume one of the permutations is $$l_1 = [e_1, \ldots, e_N]$$, and explore options for the second permutation $$l_2$$.

Your hypothesis is that the reverse ordering $$l_2 = [e_N, \ldots, e_1]$$ produces the largest distance, which is $$2(1+3+\cdots+(N-1)) = 2(N/2)^2 = N^2/2$$ for even $$N$$, and $$2(2+4+\cdots+(N-1))=(N-1)(N+1)/2=\frac{N^2}{2} - \frac{1}{2}$$ for odd $$N$$. Or, as you said yourself, $$\lfloor N^2/2\rfloor$$.

Claim: given a permutation $$l_2 = [e_{i_1}, \ldots, e_{i_N}]$$, if there is a pair $$i_j < i_k$$ for some $$j < k$$, swapping them will produce a greater difference from $$l_1$$.

Proof: the two elements $$e_{i_j}$$ and $$e_{i_k}$$ contribute $$|i_j-j| + |i_k-k|$$ to the formula for the difference between $$l_2$$ and $$l_1$$. If we swap the two elements, they instead contribute $$|i_j - k| + |i_k - j|.$$ Using the inequalities $$i_j < i_k$$ and $$j, you can show with some casework that $$|i_j-j| + |i_k-k| \le |i_j - k| + |i_k - j|,$$ so making this swap will either increase the difference or keep it the same.

Using the claim to prove that $$\lfloor N^2/2\rfloor$$ is the maximum difference. Suppose $$l_2 = [e_{i_1}, \ldots, e_{i_N}]$$ has the maximum difference with $$l_1$$. If $$l_2 = [e_N, \ldots, e_1]$$ then we are finished. Otherwise, there exists some pair $$i_j < i_k$$ where $$j < k$$. Because $$l_2$$ has the maximum distance, this swap cannot increase the difference with $$l_1$$, so it will keep the difference with $$l_1$$ the same. We can repeat this argument with the new permutation. Eventually after many swaps we will go through a sequence of permutations all while maintaining the same difference with $$l_1$$, and end up with $$[e_N, \ldots, e_1]$$, which implies that the original permutation had difference $$\lfloor N^2/2\rfloor$$ with $$l_1$$.