Количество троек, индексы и элементы которых расположены в порядке возрастания

Дан массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы найти количество троек, индексы и элементы которых расположены в порядке возрастания.

Примеры:

Input: arr[] = {1, 2, 4, 3}
Output: 2
Explanation: There are 2 possible triplets in the given array such that the elements are in increasing order, i.e, {1, 2, 4} and {1, 2, 3}.

Input: arr[] = {1, 2, 3, 4, 5}
Output: 10

Наивный подход: данная проблема может быть решена путем перебора всех возможных троек (i, j, k) заданного массива и отслеживания количества троек, чьи индексы и элементы в этих индексах расположены в порядке возрастания. После проверки всех троек выведите общее количество полученных троек.

Временная сложность: O(N ³ )
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход также можно оптимизировать, заметив, что для любого заданного индекса i количество троек, имеющих arr[i] в качестве своего среднего элемента, будет равно количеству целых чисел, меньших, чем arr[i] в диапазоне [1] . , i – 1] * количество целых чисел больше arr[i] в диапазоне [i + 1, N]. Ниже приведены шаги, которые необходимо выполнить для решения данной проблемы, используя приведенное выше наблюдение:

• Инициализируйте переменную totalCount как 0, которая хранит количество допустимых троек.
• Перебрать массив arr[] в диапазоне [1, N – 2], используя переменную i , и выполнить следующие шаги:
  • Подсчитайте количество значений меньше, чем arr[i] в диапазоне [0, i – 1] и сохраните значение в переменной K1 .
  • Подсчитайте количество значений больше, чем arr[i] в диапазоне [i + 1, N – 1] и сохраните значение в переменной K2 .
  • Добавьте значение K1*K2 к totalCount .
• Значение, хранящееся в totalCount , является требуемым ответом.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: O(1)