Максимальное количество различных инверсий в массиве

Question

Учитывая массив A из n целых чисел, мы говорим, что пара индексов i < j∈ [n] является инверсией в A, если A [i]> A [j]. Каково максимальное количество различных инверсий, которые могут иметь А?

ли
а) п - 1
б) п
с) п (п-1)/2
д) п^2
е) п (п-1) (2п 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 в описании проблемы. (Они немного разные. Вам нужно будет сделать небольшое количество алгебр.)