Максимальное количество подмассивов, содержащих максимальный и минимальный элемент массива, после удаления не более одного элемента

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

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

Примеры:

Input: arr[] = {7, 2, 5, 4, 3, 1} 
Output: 4 
Explanation: 
Delete 1 from the array then resultant array will be {7, 2, 5, 4, 3}. So the number of subarrays which contain maximum element 7 and minimum element 2 will be 4 {[7, 2], [7, 2, 5], [7, 2, 5, 4], [7, 2, 5, 4, 3]} 
 

Input: arr[] = {9, 9, 8, 9, 8, 9, 9, 8, 9, 8} 
Output: 43

Наивный подход: самый простой подход — удалить каждый элемент, а затем подсчитать количество подмассивов, имеющих минимальный и максимальный элементы результирующего массива.

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

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

  1. Инициализируйте общий результат с помощью INT_MIN.
  2. Создайте функцию say proc , которая возвращает количество подмассивов, содержащих наименьший и наибольший элементы массива.
  3. Чтобы вычислить количество подмассивов, найдите начальный и конечный индекс подмассива, используя подход с двумя указателями:
    • Инициализируйте самый маленький и самый большой элемент, скажем, низкий и высокий с последним элементом массива.
    • Инициализируйте два указателя p1 и p2 последним индексом массива, в котором хранится расположение low и high .
    • Теперь выполните итерацию по массиву и проверьте, меньше ли текущий элемент, чем low , а затем обновите p1 .
    • Если текущий элемент больше чем high , то обновить p2 .
    • На каждом шаге обновляйте максимальное количество подмассивов.
  4. Теперь подсчитайте количество подмассивов в следующих трех случаях:
    • Без удаления какого-либо элемента
    • После удаления самого большого элемента
    • После удаления самого маленького элемента.
  5. Возьмем максимум из всех трех случаев.

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

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

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