Максимальное количество подмассивов, содержащих максимальный и минимальный элемент массива, после удаления не более одного элемента
Дан массив 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)
Эффективный подход: этот подход основан на наблюдении, что удаление элементов, отличных от максимального или минимального элемента, никогда не максимизирует общий результат. Ниже приведены шаги:
- Инициализируйте общий результат с помощью INT_MIN.
- Создайте функцию say proc , которая возвращает количество подмассивов, содержащих наименьший и наибольший элементы массива.
- Чтобы вычислить количество подмассивов, найдите начальный и конечный индекс подмассива, используя подход с двумя указателями:
- Инициализируйте самый маленький и самый большой элемент, скажем, низкий и высокий с последним элементом массива.
- Инициализируйте два указателя p1 и p2 последним индексом массива, в котором хранится расположение low и high .
- Теперь выполните итерацию по массиву и проверьте, меньше ли текущий элемент, чем low , а затем обновите p1 .
- Если текущий элемент больше чем high , то обновить p2 .
- На каждом шаге обновляйте максимальное количество подмассивов.
- Теперь подсчитайте количество подмассивов в следующих трех случаях:
- Без удаления какого-либо элемента
- После удаления самого большого элемента
- После удаления самого маленького элемента.
- Без удаления какого-либо элемента
- Возьмем максимум из всех трех случаев.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство : O(N)