Сделать данный массив массивом Mountain, удалив минимальное количество элементов
Учитывая массив arr[] длины N , задача состоит в том, чтобы удалить минимальное количество элементов из массива, чтобы сделать его горным массивом, а затем распечатать его.
Note: A mountain array is an array where there is an index i such that arr[0] < arr[1] < . . .< arr[i-1] < arr[i] > arr[i+1] > . . . > arr[N-1]. Also a mountain array must have a length greater than or equal to 3 to satisfy the above condition.
Примеры:
Input: arr[] = {9, 8, 1, 7, 6, 5, 4, 3, 2, 1}
Output: 1 7 6 5 4 3 2 1
Explanation: Remove the elements 9, 8. The resultant array is the mountain array.
It is the minimum number of removals possible.Input: arr[] = {1, 1, 1};
Output: -1
Explanation: This array cannot be transformed into a mountain array
Подход: выполните следующие шаги, чтобы решить эту проблему:
- Создайте два массива слева и справа .
- Для каждого индекса i в left[i] будет храниться самая длинная возрастающая подпоследовательность, которая заканчивается на i , а в right[i] будет храниться самая длинная убывающая подпоследовательность, начинающаяся с i.
- Теперь найдите максимальную длину подпоследовательности гор, считая каждый индекс вершиной горы.
Length of mountain subsequence having peak at i = left[i]+right[i]-1
- Найдите максимальную длину подпоследовательности гор, скажем max , и отследите вершину, для которой достигается максимальная длина.
- Итак, минимальное количество удалений равно (N – max) .
- Теперь выведите самую длинную возрастающую подпоследовательность от начала до i и самую длинную убывающую подпоследовательность от i до конца массива.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N 2 )
Вспомогательное пространство: O(N)