Подсчет подмассивов с элементами в порядке возрастания-убывания или наоборот
Учитывая массив 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)