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>
Producción:
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