Dada una array arr[] de longitud N , la tarea es eliminar la cantidad mínima de elementos de la array para convertirla en una array montañosa y luego imprimirla.
Nota: Una array de montaña es una array donde hay un índice i tal que arr[0] < arr[1] < . . .< arr[i-1] < arr[i] > arr[i+1] > . . . > arr[N-1]. Además, un conjunto de montañas debe tener una longitud mayor o igual a 3 para satisfacer la condición anterior.
Ejemplos:
Entrada: arr[] = {9, 8, 1, 7, 6, 5, 4, 3, 2, 1}
Salida: 1 7 6 5 4 3 2 1
Explicación: elimine los elementos 9, 8. La array resultante es la array de la montaña.
Es el mínimo número de eliminaciones posibles.Entrada: arr[] = {1, 1, 1};
Salida: -1
Explicación: Esta array no se puede transformar en una array de montaña
Enfoque: siga los pasos a continuación para resolver este problema:
- Cree dos arrays izquierda y derecha .
- Para cada índice i , left[i] almacenará la subsecuencia creciente más larga que termina en i y right[i] almacenará la subsecuencia decreciente más larga que comienza en i.
- Ahora, encuentre la longitud máxima de la subsecuencia de la montaña asumiendo que cada índice es el pico de la montaña.
Longitud de la subsecuencia montañosa que tiene un pico en i = izquierda[i]+derecha[i]-1
- Encuentre la longitud máxima de la subsecuencia de montaña, digamos max y realice un seguimiento del pico para el que se alcanza la longitud máxima.
- Entonces, el número mínimo de eliminaciones es (N – max) .
- Ahora imprima la subsecuencia creciente más larga desde el inicio hasta i y la subsecuencia decreciente más larga desde i hasta el final de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the mountain array
// after minimum removals
void mountArray(vector<int>& arr)
{
int N = arr.size();
vector<int> left(N, 1), right(N, 1);
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= i; ++j) {
if (arr[j] < arr[i]) {
// This means the
// previous number is
// smaller than the number
left[i] = max(left[j] + 1, left[i]);
}
}
}
// Find the longest decreasing sequence
for (int i = N - 1; i >= 0; --i) {
for (int j = i; j <= N - 1; ++j) {
if (arr[j] < arr[i]) {
right[i] = max(right[j] + 1, right[i]);
}
}
}
int max = 0;
int index = 0;
for (int i = 1; i < N - 1; ++i) {
if (left[i] != 1 && right[i] != 1) {
if (max < (left[i] + right[i]) - 1) {
index = i;
max = (left[i] + right[i]) - 1;
}
}
}
// Print the longest continuous
// subsequence from 0 to ith
// and ith to N index
vector<int> left1;
left1.push_back(arr[index]);
for (int i = index; i >= 0; --i) {
if (arr[i] < arr[index]) {
// There is possibility
// either the index is
// used or not
if (left[i] + 1 == left[index]) {
left1.push_back(arr[i]);
left[index] -= 1;
}
}
}
vector<int> right1;
// Starting the right
for (int i = index; i < right.size(); ++i) {
if (arr[index] > arr[i]) {
if (right[i] + 1 == right[index]) {
right1.push_back(arr[i]);
right[index] -= 1;
}
}
}
if (max < 3) {
cout << (-1) << "\n";
}
else {
// Print the first left1 array
// then the right array
for (int i = left1.size() - 1; i >= 0; --i) {
cout << left1[i] << " ";
}
for (int i = 0; i < right1.size(); ++i) {
cout << right1[i] << " ";
}
}
}
// Driver code
int main()
{
vector<int> arr = { 9, 8, 1, 7, 6, 5, 4, 3, 2, 1 };
mountArray(arr);
}
// This code is contributed by Taranpreet
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to print the mountain array
// after minimum removals
public static void mountArray(int arr[])
{
int N = arr.length;
int left[] = new int[N];
int right[] = new int[N];
Arrays.fill(left, 1);
Arrays.fill(right, 1);
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= i; ++j) {
if (arr[j] < arr[i]) {
// This means the
// previous number is
// smaller than the number
left[i] = Math.max(left[j]
+ 1,
left[i]);
}
}
}
// Find the longest decreasing sequence
for (int i = N - 1; i >= 0; --i) {
for (int j = i; j <= N - 1; ++j) {
if (arr[j] < arr[i]) {
right[i]
= Math.max(right[j]
+ 1,
right[i]);
}
}
}
int max = 0;
int index = 0;
for (int i = 1; i < N - 1; ++i) {
if (left[i] != 1
&& right[i] != 1) {
if (max < (left[i]
+ right[i])
- 1) {
index = i;
max = (left[i]
+ right[i])
- 1;
}
}
}
// Print the longest continuous
// subsequence from 0 to ith
// and ith to N index
ArrayList<Integer> left1
= new ArrayList<Integer>();
left1.add(arr[index]);
for (int i = index; i >= 0; --i) {
if (arr[i] < arr[index]) {
// There is possibility
// either the index is
// used or not
if (left[i] + 1 == left[index]) {
left1.add(arr[i]);
left[index] -= 1;
}
}
}
ArrayList<Integer> right1
= new ArrayList<>();
// Starting the right
for (int i = index; i
< right.length;
++i) {
if (arr[index] > arr[i]) {
if (right[i] + 1
== right[index]) {
right1.add(arr[i]);
right[index] -= 1;
}
}
}
if (max < 3) {
System.out.println(-1);
}
else {
// Print the first left1 array
// then the right array
for (int i = left1.size() - 1;
i >= 0; --i) {
System.out.print(left1.get(i)
+ " ");
}
for (int i = 0; i < right1.size();
++i) {
System.out.print(right1.get(i)
+ " ");
}
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 9, 8, 1, 7, 6, 5, 4, 3, 2, 1 };
mountArray(arr);
}
}
Python3
# python3 program for the above approach
# Function to print the mountain array
# after minimum removals
def mountArray(arr):
N = len(arr)
left, right = [1 for _ in range(N)], [1 for _ in range(N)]
for i in range(0, N):
for j in range(0, i+1):
if (arr[j] < arr[i]):
# This means the
# previous number is
# smaller than the number
left[i] = max(left[j] + 1, left[i])
# Find the longest decreasing sequence
for i in range(N-1, -1, -1):
for j in range(i, N):
if (arr[j] < arr[i]):
right[i] = max(right[j] + 1, right[i])
maxi = 0
index = 0
for i in range(1, N-1):
if (left[i] != 1 and right[i] != 1):
if (maxi < (left[i] + right[i]) - 1):
index = i
maxi = (left[i] + right[i]) - 1
# Print the longest continuous
# subsequence from 0 to ith
# and ith to N index
left1 = []
left1.append(arr[index])
for i in range(index, -1, -1):
if (arr[i] < arr[index]):
# There is possibility
# either the index is
# used or not
if (left[i] + 1 == left[index]):
left1.append(arr[i])
left[index] -= 1
right1 = []
# Starting the right
for i in range(index, len(right)):
if (arr[index] > arr[i]):
if (right[i] + 1 == right[index]):
right1.append(arr[i])
right[index] -= 1
if (maxi < 3):
print("-1")
else:
# Print the first left1 array
# then the right array
for i in range(len(left1) - 1, -1, -1):
print(left1[i], end=" ")
for i in range(0, len(right1)):
print(right1[i], end=" ")
# Driver code
if __name__ == "__main__":
arr = [9, 8, 1, 7, 6, 5, 4, 3, 2, 1]
mountArray(arr)
# This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections;
class GFG {
// Function to print the mountain array
// after minimum removals
static void mountArray(int []arr)
{
int N = arr.Length;
int []left = new int[N];
int []right = new int[N];
for(int i = 0; i < N; i++) {
left[i] = 1;
right[i] = 1;
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= i; ++j) {
if (arr[j] < arr[i]) {
// This means the
// previous number is
// smaller than the number
left[i] = Math.Max(left[j]
+ 1,
left[i]);
}
}
}
// Find the longest decreasing sequence
for (int i = N - 1; i >= 0; --i) {
for (int j = i; j <= N - 1; ++j) {
if (arr[j] < arr[i]) {
right[i]
= Math.Max(right[j]
+ 1,
right[i]);
}
}
}
int max = 0;
int index = 0;
for (int i = 1; i < N - 1; ++i) {
if (left[i] != 1
&& right[i] != 1) {
if (max < (left[i]
+ right[i])
- 1) {
index = i;
max = (left[i]
+ right[i])
- 1;
}
}
}
// Print the longest continuous
// subsequence from 0 to ith
// and ith to N index
ArrayList left1 = new ArrayList();
left1.Add(arr[index]);
for (int i = index; i >= 0; --i) {
if (arr[i] < arr[index]) {
// There is possibility
// either the index is
// used or not
if (left[i] + 1 == left[index]) {
left1.Add(arr[i]);
left[index] -= 1;
}
}
}
ArrayList right1 = new ArrayList();
// Starting the right
for (int i = index; i
< right.Length;
++i) {
if (arr[index] > arr[i]) {
if (right[i] + 1
== right[index]) {
right1.Add(arr[i]);
right[index] -= 1;
}
}
}
if (max < 3) {
Console.Write(-1);
}
else {
// Print the first left1 array
// then the right array
for (int i = left1.Count - 1;
i >= 0; --i) {
Console.Write(left1[i]
+ " ");
}
for (int i = 0; i < right1.Count;
++i) {
Console.Write(right1[i]
+ " ");
}
}
}
// Driver code
public static void Main()
{
int []arr = { 9, 8, 1, 7, 6, 5, 4, 3, 2, 1 };
mountArray(arr);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to print the mountain array
// after minimum removals
function mountArray(arr) {
let N = arr.length;
let left = new Array(N).fill(1);
let right = new Array(N).fill(1);
for (let i = 0; i < N; ++i) {
for (let j = 0; j <= i; ++j) {
if (arr[j] < arr[i]) {
// This means the
// previous number is
// smaller than the number
left[i] = Math.max(left[j]
+ 1,
left[i]);
}
}
}
// Find the longest decreasing sequence
for (let i = N - 1; i >= 0; --i) {
for (let j = i; j <= N - 1; ++j) {
if (arr[j] < arr[i]) {
right[i]
= Math.max(right[j]
+ 1,
right[i]);
}
}
}
let max = 0;
let index = 0;
for (let i = 1; i < N - 1; ++i) {
if (left[i] != 1
&& right[i] != 1) {
if (max < (left[i]
+ right[i])
- 1) {
index = i;
max = (left[i]
+ right[i])
- 1;
}
}
}
// Print the longest continuous
// subsequence from 0 to ith
// and ith to N index
let left1
= [];
left1.push(arr[index]);
for (let i = index; i >= 0; --i) {
if (arr[i] < arr[index]) {
// There is possibility
// either the index is
// used or not
if (left[i] + 1 == left[index]) {
left1.push(arr[i]);
left[index] -= 1;
}
}
}
let right1
= []
// Starting the right
for (let i = index; i
< right.length;
++i) {
if (arr[index] > arr[i]) {
if (right[i] + 1
== right[index]) {
right1.push(arr[i]);
right[index] -= 1;
}
}
}
if (max < 3) {
document.write(-1);
}
else {
// Print the first left1 array
// then the right array
for (let i = left1.length - 1;
i >= 0; --i) {
document.write(left1[i]
+ " ");
}
for (let i = 0; i < right1.length;
++i) {
document.write(right1[i]
+ " ");
}
}
}
// Driver code
let arr = [9, 8, 1, 7, 6, 5, 4, 3, 2, 1];
mountArray(arr);
// This code is contributed by Potta Lokesh
</script>
Producción
1 7 6 5 4 3 2 1
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA