Maximum single-sell profits

Question

The question Maximum single-sell profit returns one pair. How can you build upon any of the sub O(n^2) algorithm to find all pairs sorted by profit?

Ex.

values: scala.collection.immutable.Vector[Int] = Vector(1, 5, 10, -5, 0, -10, 15)
pairsAsc: Vector[(Int, Int)] = Vector((5,6), (3,6), (0,6), (0,2), (3,4))
gains: scala.collection.immutable.Vector[Int] = Vector(25, 20, 14, 9, 5)

Answer 1

It's Sorting-X+Y-hard, so it's unreasonable to expect an o(n^2 log n)-time algorithm (in some reasonable model of computation).

The reduction is, given arrays x₁, … x_n > 0 and y₁, … y_n > 0, let Z > max(x₁, … x_n, y₁, … y_n). Let the input to this problem be Z - x₁, …, Z - x_n, 3Z + y₁, …, 3Z + y_n. All of the X-X differences and Y-Y differences are less than Z. All of the X-Y differences are greater than Z. This makes it easy to filter the output, solving the original problem.