数组中不同反转的最大数量

Question

给定一个包含 n 个整数的数组 A，如果 A[i]>A[j]，我们说一对索引 i

是吗
a) n - 1
b) n
c) n(n−1)/2
d) n^2
e) n(n−1)(2n−1)/6

Answer 1

嗯，所有对不同的索引显然可能是倒置的（如果整个数组是倒序的，例如：[5,4,3,2, 1]). 显然不可能超过所有对不同的索引是倒置的。

所以问题是：有多少对不同的索引？

如果按几何排列，图案很清晰：

(1,2) (1,3) (1,4) (1,5)
      (2,3) (2,4) (2,5)
            (3,4) (3,5)
                  (4,5)

（请注意，我没有包括 (2,1)，因为这两个索引与 (1,2) 相同。）

出于显而易见的原因，此类数字被称为 triangular numbers。维基百科给出了一个公式，但一定不要将其公式中的 n 与问题陈述中的 n 混淆。（它们略有不同。您需要做一些代数运算。）

Maximum number of distinct inversions in an array