Подсчет подмассивов, начинающихся или заканчивающихся индексом i, таким образом, что arr[i] является максимальным в подмассиве

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

Примеры:

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

1. The subarray starting or ending at index 0 and with maximum arr[0](=3) is {3}. Therefore, the count is 1.
2. The subarrays starting or ending at index 1 and with maximum arr[1](=4) are {3, 4}, {4}, and {4, 1}. Therefore, the count is 3.
3. The subarray starting or ending at index 2 and with maximum arr[2](=1) is {1}. Therefore, the count is 1.
4. The subarrays starting or ending at index 3 and with maximum arr[3](=6) are {3, 4, 1, 6}, {4, 1, 6}, {1, 6}, {6}, and {6, 2}. Therefore, the count is 5.
5. The subarray starting or ending at index 4 and with maximum arr[4](=2) is {2}. Therefore, the count is 1.

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

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы для каждого i ^-го индекса выполнять итерацию назад и вперед, пока максимум подмассива не останется равным arr[i] , а затем вывести общее количество полученных подмассивов.

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

Эффективный подход. Описанный выше подход можно оптимизировать, сохраняя индекс следующего большего элемента и предыдущего большего элемента для каждого индекса i и соответственно находя количество подмассивов для каждого индекса. Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте два массива, скажем, pge[] и nge[] для хранения индекса предыдущего большего элемента и следующего большего элемента для каждого индекса i .
• Найдите индекс предыдущего большего элемента для каждого индекса и сохраните полученный массив в pge[] .
• Найдите индекс следующего большего элемента для каждого индекса и сохраните полученный массив в nge[] .
• Перебрать диапазон [0, N – 1] и использовать переменную i , и в каждой итерации вывести количество подмассивов, начинающихся или заканчивающихся на индексе i , и с arr[i] как максимальным как nge[i] + pge[i ] – 1 и распечатайте это количество.

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

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