Подсчет подмассивов с наибольшим элементом, по крайней мере в два раза превышающим наибольший из оставшихся элементов

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

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

Примеры:

Input: arr[] = {1, 6, 10, 9, 7, 3}
Output: 4
Explanation:
Below are the subarrays satisfying the given condition:

  1. Consider the subarray {6, 10, 9, 7}. Now the maximum element of this subarray is 10 which is greater than twice the maximum elements of the remaining array elements i.e., 2*max{1, 3} = 2*3 = 6.
  2. Consider the subarray {6, 10, 9, 7, 3}. Now the maximum element of this subarray is 10 which is greater than twice the maximum elements of the remaining array elements i.e., 2*max{1} = 2*1 = 2.
  3. Consider the subarray {1, 6, 10, 9, 7}. Now the maximum element of this subarray is 10 which is greater than twice the maximum elements of the remaining array elements i.e., 2*max{3} = 2*3 = 6.
  4. Consider the subarray {1, 6, 10, 9, 7, 3}. Now the maximum element of this subarray is 10 which is greater than twice the maximum elements of the remaining array elements i.e., 2*max{} = 2*0 = 0.

Therefore, the total number of subarrays is 4.

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

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

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

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

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

  • Инициализируйте переменную, скажем, mx , которая хранит максимальный элемент массива.
  • Инициализируйте две переменные L и R для хранения левой и правой конечных точек подмассива.
  • Переберите диапазон [0, N – 1], используя переменную i , и если значение 2*arr[i] больше, чем mx , тогда инициализируйте L значением i и прервите цикл.
  • Переберите диапазон [N – 1, 0] в обратном порядке, используя переменную i , и если значение 2*arr[i] больше, чем mx , тогда инициализируйте R значением i и прервите цикл.
  • После выполнения вышеуказанных шагов выведите в качестве результата значение (L + 1)*(N – R) .

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

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

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