I have come across a question that is a bit hard to understand due to its wording, I may havecome up with a possible solution, but I don't know if it's correct. Can you please help me? Thanks in advance!
Suppose we exchange elements $a[i]$ and $a[j]$, where $j > i$, which are originally out of order.
For example, $a = [2,8,3,7,1,5,6]$ and we exchange the second and sixth elements, we have $[2,5,3,7,1,8,6]$.
The array has now fewer inversions. What is the maximum number of inversions that can be removed if we exchange $a[i]$ and $a[j]$?
My proposed answer
Take an array and sort it in reverse order. The first element would have the most inversions. We switch it with the last element and the number of inversions decrease drastically.
The maximum number of inversions would be $j-i+n-2$.
Since the question doesn't say anything about me being allowed to change the order of the array, I don't know if my proposed answer is the one they were aiming for.