Dada una array arr[] de tamaño N , la tarea es encontrar el número mínimo de elementos de la array necesarios para eliminar de la array, de modo que la array dada se convierta en una array bitónica .
Ejemplos:
Entrada: arr[] = { 2, 1, 1, 5, 6, 2, 3, 1 }
Salida: 3
Explicación:
Eliminar arr[0], arr[1] y arr[5] modifica arr[] a { 1 , 5, 6, 3, 1 }
Dado que los elementos del arreglo siguen un orden creciente seguido de un orden decreciente, la salida requerida es 3.Entrada: arr[] = { 1, 3, 1 }
Salida: 0
Explicación:
La array dada ya es una array bitónica. Por lo tanto, la salida requerida es 3.
Enfoque: El problema se puede resolver con base en el concepto del problema de la subsecuencia creciente más larga . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos left[] , tal que left[i] almacene la longitud de la subsecuencia creciente más larga hasta el i -ésimo índice.
- Inicialice una variable, digamos right[] , de modo que right[i] almacene la longitud de la subsecuencia decreciente más larga en el rango [i, N] .
- Recorra la array izquierda[] y derecha[] usando la variable i y encuentre el valor máximo de (izquierda[i] + derecha[i] – 1) y guárdelo en una variable, digamos maxLen .
- Finalmente, imprima el valor de N – maxLen .
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to count minimum array elements // required to be removed to make an array bitonic void min_element_removal(int arr[], int N) { // left[i]: Stores the length // of LIS up to i-th index vector<int> left(N, 1); // right[i]: Stores the length // of decreasing subsequence // over the range [i, N] vector<int> right(N, 1); // Calculate the length of LIS // up to i-th index for (int i = 1; i < N; i++) { // Traverse the array // upto i-th index for (int j = 0; j < i; j++) { // If arr[j] is less than arr[i] if (arr[j] < arr[i]) { // Update left[i] left[i] = max(left[i], left[j] + 1); } } } // Calculate the length of decreasing // subsequence over the range [i, N] for (int i = N - 2; i >= 0; i--) { // Traverse right[] array for (int j = N - 1; j > i; j--) { // If arr[i] is greater // than arr[j] if (arr[i] > arr[j]) { // Update right[i] right[i] = max(right[i], right[j] + 1); } } } // Stores length of the // longest bitonic array int maxLen = 0; // Traverse left[] and right[] array for (int i = 1; i < N - 1; i++) { // Update maxLen maxLen = max(maxLen, left[i] + right[i] - 1); } cout << (N - maxLen) << "\n"; } // Function to print minimum removals // required to make given array bitonic void makeBitonic(int arr[], int N) { if (N == 1) { cout << "0" << endl; return; } if (N == 2) { if (arr[0] != arr[1]) cout << "0" << endl; else cout << "1" << endl; return; } min_element_removal(arr, N); } // Driver Code int main() { int arr[] = { 2, 1, 1, 5, 6, 2, 3, 1 }; int N = sizeof(arr) / sizeof(arr[0]); makeBitonic(arr, N); return 0; }
C
// C program to implement // the above approach #include <stdio.h> #define max(a,b) ((a) > (b) ? (a) : (b)) //defining max // Function to count minimum array elements // required to be removed to make an array bitonic void min_element_removal(int arr[], int N) { // left[i]: Stores the length // of LIS up to i-th index int left[N]; for (int i = 0; i < N; i++) left[i] = 1; // right[i]: Stores the length // of decreasing subsequence // over the range [i, N] int right[N]; for (int i = 0; i < N; i++) right[i] = 1; // Calculate the length of LIS // up to i-th index for (int i = 1; i < N; i++) { // Traverse the array // upto i-th index for (int j = 0; j < i; j++) { // If arr[j] is less than arr[i] if (arr[j] < arr[i]) { // Update left[i] left[i] = max(left[i], left[j] + 1); } } } // Calculate the length of decreasing // subsequence over the range [i, N] for (int i = N - 2; i >= 0; i--) { // Traverse right[] array for (int j = N - 1; j > i; j--) { // If arr[i] is greater // than arr[j] if (arr[i] > arr[j]) { // Update right[i] right[i] = max(right[i], right[j] + 1); } } } // Stores length of the // longest bitonic array int maxLen = 0; // Traverse left[] and right[] array for (int i = 1; i < N - 1; i++) { // Update maxLen maxLen = max(maxLen, left[i] + right[i] - 1); } printf("%d\n", (N - maxLen)); } // Function to print minimum removals // required to make given array bitonic void makeBitonic(int arr[], int N) { if (N == 1) { printf("0\n"); return; } if (N == 2) { if (arr[0] != arr[1]) printf("0\n"); else printf("1\n"); return; } min_element_removal(arr, N); } // Driver Code int main() { int arr[] = { 2, 1, 1, 5, 6, 2, 3, 1 }; int N = sizeof(arr) / sizeof(arr[0]); makeBitonic(arr, N); return 0; } // This code is contributed by phalashi.
Java
// Java program to implement // the above approach class GFG { // Function to count minimum array elements // required to be removed to make an array bitonic static void min_element_removal(int arr[], int N) { // left[i]: Stores the length // of LIS up to i-th index int left[] = new int[N]; for(int i = 0; i < N; i++) left[i] = 1; // right[i]: Stores the length // of decreasing subsequence // over the range [i, N] int right[] = new int[N]; for(int i = 0; i < N; i++) right[i] = 1; // Calculate the length of LIS // up to i-th index for (int i = 1; i < N; i++) { // Traverse the array // upto i-th index for (int j = 0; j < i; j++) { // If arr[j] is less than arr[i] if (arr[j] < arr[i]) { // Update left[i] left[i] = Math.max(left[i], left[j] + 1); } } } // Calculate the length of decreasing // subsequence over the range [i, N] for (int i = N - 2; i >= 0; i--) { // Traverse right[] array for (int j = N - 1; j > i; j--) { // If arr[i] is greater // than arr[j] if (arr[i] > arr[j]) { // Update right[i] right[i] = Math.max(right[i], right[j] + 1); } } } // Stores length of the // longest bitonic array int maxLen = 0; // Traverse left[] and right[] array for (int i = 1; i < N - 1; i++) { // Update maxLen maxLen = Math.max(maxLen, left[i] + right[i] - 1); } System.out.println(N - maxLen); } // Function to print minimum removals // required to make given array bitonic static void makeBitonic(int arr[], int N) { if (N == 1) { System.out.println("0"); return; } if (N == 2) { if (arr[0] != arr[1]) System.out.println("0"); else System.out.println("1"); return; } min_element_removal(arr, N); } // Driver Code public static void main (String[] args) { int arr[] = { 2, 1, 1, 5, 6, 2, 3, 1 }; int N = arr.length; makeBitonic(arr, N); } } // This code is contributed by AnkitRai01
Python3
# Python3 program to implement # the above approach # Function to count minimum array elements # required to be removed to make an array bitonic def min_element_removal(arr, N): # left[i]: Stores the length # of LIS up to i-th index left = [1] * N # right[i]: Stores the length # of decreasing subsequence # over the range [i, N] right = [1] * (N) #Calculate the length of LIS #up to i-th index for i in range(1, N): #Traverse the array #upto i-th index for j in range(i): #If arr[j] is less than arr[i] if (arr[j] < arr[i]): #Update left[i] left[i] = max(left[i], left[j] + 1) # Calculate the length of decreasing # subsequence over the range [i, N] for i in range(N - 2, -1, -1): # Traverse right[] array for j in range(N - 1, i, -1): # If arr[i] is greater # than arr[j] if (arr[i] > arr[j]): # Update right[i] right[i] = max(right[i], right[j] + 1) # Stores length of the # longest bitonic array maxLen = 0 # Traverse left[] and right[] array for i in range(1, N - 1): # Update maxLen maxLen = max(maxLen, left[i] + right[i] - 1) print((N - maxLen)) # Function to print minimum removals # required to make given array bitonic def makeBitonic(arr, N): if (N == 1): print("0") return if (N == 2): if (arr[0] != arr[1]): print("0") else: print("1") return min_element_removal(arr, N) # Driver Code if __name__ == '__main__': arr=[2, 1, 1, 5, 6, 2, 3, 1] N = len(arr) makeBitonic(arr, N) # This code is contributed by mohit kumar 29
C#
// C# program to implement // the above approach using System; class GFG{ // Function to count minimum array elements // required to be removed to make an array bitonic static void min_element_removal(int []arr, int N) { // left[i]: Stores the length // of LIS up to i-th index int []left = new int[N]; for(int i = 0; i < N; i++) left[i] = 1; // right[i]: Stores the length // of decreasing subsequence // over the range [i, N] int []right = new int[N]; for(int i = 0; i < N; i++) right[i] = 1; // Calculate the length of LIS // up to i-th index for(int i = 1; i < N; i++) { // Traverse the array // upto i-th index for(int j = 0; j < i; j++) { // If arr[j] is less than arr[i] if (arr[j] < arr[i]) { // Update left[i] left[i] = Math.Max(left[i], left[j] + 1); } } } // Calculate the length of decreasing // subsequence over the range [i, N] for(int i = N - 2; i >= 0; i--) { // Traverse right[] array for(int j = N - 1; j > i; j--) { // If arr[i] is greater // than arr[j] if (arr[i] > arr[j]) { // Update right[i] right[i] = Math.Max(right[i], right[j] + 1); } } } // Stores length of the // longest bitonic array int maxLen = 0; // Traverse left[] and right[] array for(int i = 1; i < N - 1; i++) { // Update maxLen maxLen = Math.Max(maxLen, left[i] + right[i] - 1); } Console.WriteLine(N - maxLen); } // Function to print minimum removals // required to make given array bitonic static void makeBitonic(int []arr, int N) { if (N == 1) { Console.WriteLine("0"); return; } if (N == 2) { if (arr[0] != arr[1]) Console.WriteLine("0"); else Console.WriteLine("1"); return; } min_element_removal(arr, N); } // Driver Code public static void Main(String[] args) { int []arr = { 2, 1, 1, 5, 6, 2, 3, 1 }; int N = arr.Length; makeBitonic(arr, N); } } // This code is contributed by AnkThon
Javascript
<script> // Javascript program to implement // the above approach // Function to count minimum array elements // required to be removed to make an array bitonic function min_element_removal(arr, N) { // left[i]: Stores the length // of LIS up to i-th index var left = Array(N).fill(1); // right[i]: Stores the length // of decreasing subsequence // over the range [i, N] var right = Array(N).fill(1); // Calculate the length of LIS // up to i-th index for (var i = 1; i < N; i++) { // Traverse the array // upto i-th index for (var j = 0; j < i; j++) { // If arr[j] is less than arr[i] if (arr[j] < arr[i]) { // Update left[i] left[i] = Math.max(left[i], left[j] + 1); } } } // Calculate the length of decreasing // subsequence over the range [i, N] for (var i = N - 2; i >= 0; i--) { // Traverse right[] array for (var j = N - 1; j > i; j--) { // If arr[i] is greater // than arr[j] if (arr[i] > arr[j]) { // Update right[i] right[i] = Math.max(right[i], right[j] + 1); } } } // Stores length of the // longest bitonic array var maxLen = 0; // Traverse left[] and right[] array for (var i = 1; i < N - 1; i++) { // Update maxLen maxLen = Math.max(maxLen, left[i] + right[i] - 1); } document.write((N - maxLen) + "<br>"); } // Function to print minimum removals // required to make given array bitonic function makeBitonic(arr, N) { if (N == 1) { document.write( "0" + "<br>"); return; } if (N == 2) { if (arr[0] != arr[1]) document.write( "0" + "<br>"); else document.write( "1" + "<br>"); return; } min_element_removal(arr, N); } // Driver Code var arr = [2, 1, 1, 5, 6, 2, 3, 1]; var N = arr.length; makeBitonic(arr, N); // This code is contributed by rutvik_56. </script>
3
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA