Dados tres números enteros N , bajo y alto , la tarea es encontrar la secuencia bitónica lexicográficamente más grande que consta de N elementos que se encuentran en el rango [bajo, alto] . Si no es posible generar tal secuencia, imprima «No es posible» .
Ejemplos:
Entrada: N = 5, bajo = 2, alto = 6
Salida: 5 6 5 4 3
Explicación:
La secuencia {arr[0], arr[1]} es estrictamente creciente seguida de una secuencia estrictamente decreciente de los elementos restantes. Esta secuencia es la lexicográficamente más grande posible con todos los elementos en el rango [2, 6] y la longitud de esta secuencia es 5.Entrada: N = 10, bajo = 4, alto = 10
Salida: 7 8 9 10 9 8 7 6 5 4
Enfoque: La idea es encontrar el índice adecuado de alto en la secuencia resultante y luego mantener una diferencia de 1 entre los elementos adyacentes en la secuencia de modo que la secuencia bitónica formada sea lo lexicográficamente más grande posible. Siga los pasos a continuación para resolver el problema:
- Inicialice una array A[] de tamaño N para almacenar la secuencia resultante.
- Inicialice una variable high_index = -1 para almacenar el índice de high en A[] y establezca high_index = N – (high – low + 1) .
- Si high_index > (N – 1) / 2 , los N/2 elementos restantes no se pueden colocar en orden estrictamente creciente. Por lo tanto, imprima «No es posible».
- De lo contrario, realice los siguientes pasos:
- Si high_index ≤ 0 , establezca high_index = 1 ya que tiene que haber una secuencia estrictamente creciente al principio.
- Mantenga una secuencia estrictamente decreciente con una diferencia de 1 desde el rango [high_index, 0] , comenzando con un valor alto .
- Mantenga una secuencia estrictamente decreciente con una diferencia de 1 desde el rango [high_index + 1, N – 1] comenzando con un valor (high – 1) .
- Después de completar los pasos anteriores, imprima todos los elementos en la array A[] .
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 find the lexicographically // largest bitonic sequence of size N // elements lies in the range[low, high] void LargestArray(int N, int low, int high) { // Store index of highest element int high_index = N - (high - low + 1); // If high_index > (N-1)/2, then // remaining N/2 elements cannot // be placed in bitonic order if (high_index > (N - 1) / 2) { cout << "Not Possible"; return; } // If high_index <= 0, then // set high_index as 1 if (high_index <= 0) high_index = 1; // Stores the resultant sequence int A[N]; // Store the high value int temp = high; // Maintain strictly decreasing // sequence from index high_index // to 0 starting with temp for (int i = high_index; i >= 0; i--) { // Store the value and decrement // the temp variable by 1 A[i] = temp--; } // Maintain the strictly decreasing // sequence from index high_index + 1 // to N - 1 starting with high - 1 high -= 1; for (int i = high_index + 1; i < N; i++) // Store the value and decrement // high by 1 A[i] = high--; // Print the resultant sequence for (int i = 0; i < N; i++) { cout << A[i] << ' '; } } // Driver Code int main() { int N = 5, low = 2, high = 6; // Function Call LargestArray(N, low, high); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the lexicographically // largest bitonic sequence of size N // elements lies in the range[low, high] static void LargestArray(int N, int low, int high) { // Store index of highest element int high_index = N - (high - low + 1); // If high_index > (N-1)/2, then // remaining N/2 elements cannot // be placed in bitonic order if (high_index > (N - 1) / 2) { System.out.print("Not Possible"); return; } // If high_index <= 0, then // set high_index as 1 if (high_index <= 0) high_index = 1; // Stores the resultant sequence int[] A = new int[N]; // Store the high value int temp = high; // Maintain strictly decreasing // sequence from index high_index // to 0 starting with temp for(int i = high_index; i >= 0; i--) { // Store the value and decrement // the temp variable by 1 A[i] = temp--; } // Maintain the strictly decreasing // sequence from index high_index + 1 // to N - 1 starting with high - 1 high -= 1; for(int i = high_index + 1; i < N; i++) // Store the value and decrement // high by 1 A[i] = high--; // Print the resultant sequence for(int i = 0; i < N; i++) { System.out.print(A[i] + " "); } } // Driver Code public static void main(String[] args) { int N = 5, low = 2, high = 6; // Function Call LargestArray(N, low, high); } } // This code is contributed by susmitakundugoaldanga
Python3
# Python3 program for the above approach # Function to find the lexicographically # largest bitonic sequence of size N # elements lies in the range[low, high] def LargestArray(N, low, high): # Store index of highest element high_index = N - (high - low + 1) # If high_index > (N-1)/2, then # remaining N/2 elements cannot # be placed in bitonic order if (high_index > (N - 1) // 2): print("Not Possible") return # If high_index <= 0, then # set high_index as 1 if (high_index <= 0): high_index = 1 # Stores the resultant sequence A = [0] * N # Store the high value temp = high # Maintain strictly decreasing # sequence from index high_index # to 0 starting with temp for i in range(high_index, -1, -1): # Store the value and decrement # the temp variable by 1 A[i] = temp temp = temp - 1 # Maintain the strictly decreasing # sequence from index high_index + 1 # to N - 1 starting with high - 1 high -= 1 for i in range(high_index + 1, N): # Store the value and decrement # high by 1 A[i] = high high = high - 1 # Print the resultant sequence for i in range(N): print(A[i], end = " ") # Driver Code N = 5 low = 2 high = 6 # Function Call LargestArray(N, low, high) # This code is contributed by code_hunt
C#
// C# program for the above approach using System; class GFG{ // Function to find the lexicographically // largest bitonic sequence of size N // elements lies in the range[low, high] static void LargestArray(int N, int low, int high) { // Store index of highest element int high_index = N - (high - low + 1); // If high_index > (N-1)/2, then // remaining N/2 elements cannot // be placed in bitonic order if (high_index > (N - 1) / 2) { Console.Write("Not Possible"); return; } // If high_index <= 0, then // set high_index as 1 if (high_index <= 0) high_index = 1; // Stores the resultant sequence int[] A = new int[N]; // Store the high value int temp = high; // Maintain strictly decreasing // sequence from index high_index // to 0 starting with temp for(int i = high_index; i >= 0; i--) { // Store the value and decrement // the temp variable by 1 A[i] = temp--; } // Maintain the strictly decreasing // sequence from index high_index + 1 // to N - 1 starting with high - 1 high -= 1; for(int i = high_index + 1; i < N; i++) // Store the value and decrement // high by 1 A[i] = high--; // Print the resultant sequence for(int i = 0; i < N; i++) { Console.Write(A[i] + " "); } } // Driver Code public static void Main(String[] args) { int N = 5, low = 2, high = 6; // Function Call LargestArray(N, low, high); } } // This code is contributed by shivanisinghss2110
Javascript
<script> // Javascript program for the above approach // Function to find the lexicographically // largest bitonic sequence of size N // elements lies in the range[low, high] function LargestArray(N, low, high) { // Store index of highest element let high_index = N - (high - low + 1); // If high_index > (N-1)/2, then // remaining N/2 elements cannot // be placed in bitonic order if (high_index > (N - 1) / 2) { document.write("Not Possible"); return; } // If high_index <= 0, then // set high_index as 1 if (high_index <= 0) high_index = 1; // Stores the resultant sequence let A = []; // Store the high value let temp = high; // Maintain strictly decreasing // sequence from index high_index // to 0 starting with temp for(let i = high_index; i >= 0; i--) { // Store the value and decrement // the temp variable by 1 A[i] = temp--; } // Maintain the strictly decreasing // sequence from index high_index + 1 // to N - 1 starting with high - 1 high -= 1; for(let i = high_index + 1; i < N; i++) // Store the value and decrement // high by 1 A[i] = high--; // Print the resultant sequence for(let i = 0; i < N; i++) { document.write(A[i] + " "); } } // Driver Code let N = 5, low = 2, high = 6; // Function Call LargestArray(N, low, high); </script>
5 6 5 4 3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA