Dada una array A[] de tamaño N , la tarea es encontrar la longitud del subconjunto estrictamente creciente más largo con cada par de elementos adyacentes que satisfagan la condición A[i + 1] ≤ 2 * A[i] . Si hay varios subconjuntos de este tipo, imprima cualquiera de ellos.
Ejemplos:
Entrada: A[] = {3, 1, 5, 11}
Salida: 3, 5
Explicación: Entre todos los subconjuntos posibles de la array, {3, 5} es el subconjunto más largo que satisface la condición dada.Entrada: A[] = {3, 1, 7, 12}
Salida: 7, 12
Explicación: Entre todos los subconjuntos posibles del arreglo, {7, 12} es el subconjunto más largo que satisface la condición dada.
Enfoque ingenuo: el enfoque más simple para resolver el problema es ordenar la array en orden ascendente y generar todos los subconjuntos posibles de la array dada y encontrar la longitud del subconjunto más largo que satisfaga la condición dada.
Complejidad de Tiempo: O(N * 2 N )
Espacio Auxiliar: O(N)
Enfoque eficiente: la idea se basa en la observación de que el subconjunto más largo se generará solo cuando los elementos continuos que satisfagan la condición dada se tomen de la array ordenada .
Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos index y maxLen , para almacenar el índice inicial y la longitud máxima del subconjunto requerido.
- Ordene la array A[] en orden ascendente .
- Inicialice una variable, digamos i , para atravesar e iterar mientras i < N y realice los siguientes pasos:
- Inicialice otra variable j = i , para almacenar el punto final del subconjunto actual.
- Iterar mientras j < N – 1 y 2 * A[j] ≥ A[j + 1] es cierto e incrementar la longitud del subconjunto actual, digamos L , e incrementar j en 1 .
- Si el valor de L es mayor que maxLen , actualice maxLen a L e indexe a i .
- Actualice el valor de i a j + 1 .
- Imprime el subconjunto requerido imprimiendo los elementos en el rango [index, index+maxLen-1] .
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 length of the
// longest subset satisfying given conditions
void maxLenSubset(int a[], int n)
{
// Sort the array in ascending order
sort(a, a + n);
// Stores the starting index and maximum
// length of the required subset
int index = 0, maxlen = -1;
// Pointer to traverse the array
int i = 0;
// Iterate while i < n
while (i < n) {
// Stores end point
// of current subset
int j = i;
// Store the length of
// the current subset
int len = 1;
// Continue adding elements to the current
// subset till the condition satisfies
while (j < n - 1) {
if (2 * a[j] >= a[j + 1]) {
// Increment length of
// the current subset
len++;
}
else
break;
// Increment the pointer j
j++;
}
// If length of the current subset
// exceeds overall maximum length
if (maxlen < len) {
// Update maxlen
maxlen = len;
// Update index
index = i;
}
// Increment j
j++;
// Update i
i = j;
}
// Store the starting index of
// the required subset in i
i = index;
// Print the required subset
while (maxlen > 0) {
// Print the array element
cout << a[i] << " ";
// Decrement maxlen
maxlen--;
// Increment i
i++;
}
}
// Driver Code
int main()
{
// Given array
int a[] = { 3, 1, 5, 11 };
// Store the size of the array
int n = sizeof(a) / sizeof(int);
maxLenSubset(a, n);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to find the length of the
// longest subset satisfying given conditions
static void maxLenSubset(int a[], int n)
{
// Sort the array in ascending order
Arrays.sort(a);
// Stores the starting index and maximum
// length of the required subset
int index = 0, maxlen = -1;
// Pointer to traverse the array
int i = 0;
// Iterate while i < n
while (i < n)
{
// Stores end point
// of current subset
int j = i;
// Store the length of
// the current subset
int len = 1;
// Continue adding elements to the current
// subset till the condition satisfies
while (j < n - 1)
{
if (2 * a[j] >= a[j + 1])
{
// Increment length of
// the current subset
len++;
}
else
break;
// Increment the pointer j
j++;
}
// If length of the current subset
// exceeds overall maximum length
if (maxlen < len)
{
// Update maxlen
maxlen = len;
// Update index
index = i;
}
// Increment j
j++;
// Update i
i = j;
}
// Store the starting index of
// the required subset in i
i = index;
// Print the required subset
while (maxlen > 0)
{
// Print the array element
System.out.print(a[i] + " ");
// Decrement maxlen
maxlen--;
// Increment i
i++;
}
}
// Driver Code
public static void main(String[] args)
{
// Given array
int a[] = { 3, 1, 5, 11 };
// Store the size of the array
int n = a.length;
maxLenSubset(a, n);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach # Function to find the length of the # longest subset satisfying given conditions def maxLenSubset(a, n): # Sort the array in ascending order a.sort(reverse = False) # Stores the starting index and maximum # length of the required subset index = 0 maxlen = -1 # Pointer to traverse the array i = 0 # Iterate while i < n while (i < n): # Stores end point # of current subset j = i # Store the length of # the current subset len1 = 1 # Continue adding elements to the current # subset till the condition satisfies while (j < n - 1): if (2 * a[j] >= a[j + 1]): # Increment length of # the current subset len1 += 1 else: break # Increment the pointer j j += 1 # If length of the current subset # exceeds overall maximum length if (maxlen < len1): # Update maxlen maxlen = len1 # Update index index = i # Increment j j += 1 # Update i i = j # Store the starting index of # the required subset in i i = index # Print the required subset while (maxlen > 0): # Print the array element print(a[i], end = " ") # Decrement maxlen maxlen -= 1 # Increment i i += 1 # Driver Code if __name__ == '__main__': # Given array a = [3, 1, 5, 11] # Store the size of the array n = len(a) maxLenSubset(a, n) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the length of the
// longest subset satisfying given conditions
static void maxLenSubset(int[] a, int n)
{
// Sort the array in ascending order
Array.Sort(a);
// Stores the starting index and maximum
// length of the required subset
int index = 0, maxlen = -1;
// Pointer to traverse the array
int i = 0;
// Iterate while i < n
while (i < n)
{
// Stores end point
// of current subset
int j = i;
// Store the length of
// the current subset
int len = 1;
// Continue adding elements to the current
// subset till the condition satisfies
while (j < n - 1)
{
if (2 * a[j] >= a[j + 1])
{
// Increment length of
// the current subset
len++;
}
else
break;
// Increment the pointer j
j++;
}
// If length of the current subset
// exceeds overall maximum length
if (maxlen < len)
{
// Update maxlen
maxlen = len;
// Update index
index = i;
}
// Increment j
j++;
// Update i
i = j;
}
// Store the starting index of
// the required subset in i
i = index;
// Print the required subset
while (maxlen > 0)
{
// Print the array element
Console.Write(a[i] + " ");
// Decrement maxlen
maxlen--;
// Increment i
i++;
}
}
// Driver Code
public static void Main(string[] args)
{
// Given array
int[] a = { 3, 1, 5, 11 };
// Store the size of the array
int n = a.Length;
maxLenSubset(a, n);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for
// the above approach
// Function to find the
// length of the
// longest subset satisfying
// given conditions
function maxLenSubset(a, n)
{
// Sort the array in ascending order
a.sort( function(a, b) {
return a - b;
})
// Stores the starting
// index and maximum
// length of the required subset
let index = 0, maxlen = -1;
// Pointer to traverse the array
let i = 0;
// Iterate while i < n
while (i < n) {
// Stores end point
// of current subset
let j = i;
// Store the length of
// the current subset
let len = 1;
// Continue adding elements
// to the current
// subset till the
// condition satisfies
while (j < n - 1) {
if (2 * a[j] >= a[j + 1])
{
// Increment length of
// the current subset
len++;
}
else
break;
// Increment the pointer j
j++;
}
// If length of the current subset
// exceeds overall maximum length
if (maxlen < len) {
// Update maxlen
maxlen = len;
// Update index
index = i;
}
// Increment j
j++;
// Update i
i = j;
}
// Store the starting index of
// the required subset in i
i = index;
// Print the required subset
while (maxlen > 0) {
// Print the array element
document.write(a[i]+" ")
// Decrement maxlen
maxlen--;
// Increment i
i++;
}
}
// Driver Code
// Given array
let a = [3, 1, 5, 11];
// Store the size of the array
let n = a.length
maxLenSubset(a, n)
// This code is contributed by Hritik
</script>
Producción:
3 5
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitmanathiya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA