Подсчет подмассивов с элементами в порядке возрастания-убывания или наоборот

Опубликовано: 19 Сентября, 2022

Учитывая массив arr[] размера N , задача состоит в том, чтобы найти количество подмассивов с элементами в порядке возрастания-убывания или наоборот . Подмассив { a, b, c } будет действительным тогда и только тогда, когда выполняется либо ( a < b > c ), либо ( a > b < c ).

Примеры :

Input: arr[] = {9, 8, 7, 6, 5}
Output: 4
Explanation: As each element is lesser than the other,  
only consider the sequence of length 2, four times: [9, 8], [8, 7], [7, 6], [6, 5]

Input: arr[] = {1, 2, 1, 2, 1}
Output: 10
Explanation: All possible sequences are: [1, 2, 1, 2, 1], [1, 2, 1, 2], [2, 1, 2, 1], [1, 2, 1],  
[2, 1, 2], [1, 2, 1], [1, 2], [2, 1], [1, 2], [2, 1]

Подход : задача может быть решена с использованием подхода скользящего окна и математических концепций. Решение строится с помощью следующих шагов:

  • Найдите самый длинный текущий действительный подмассив.
  • Когда текущий самый длинный действительный подмассив разрывается, возьмите длину самого длинного подмассива и сохраните ее в массиве.
  • Перезапустите окно с точки, где закончился предыдущий самый длинный подмассив, найдите следующее самое длинное окно и повторяйте, пока массив не закончится.
  • Массив будет иметь длину смежных подмассивов, которые не перекрываются .
  • Для каждого окна размера k, которое является допустимым подмассивом, все возможные окна любого размера также являются допустимыми подпоследовательностями .
  • Чтобы найти все возможные подпоследовательности в окне, если одно окно равно k, то количество всех подмассивов всех размеров = kx (k-1)/2
  • Сделайте это для каждого размера окна в массиве и добавьте его к count .
  • Возврат считается окончательным ответом.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ