Dado un arreglo arr[] que consta de N enteros y dos valores enteros L y R , que indican los índices inicial y final de un subarreglo, la tarea es verificar si existe una subsecuencia no contigua que sea igual o no al subarreglo dado. . Si es cierto, escriba “Sí” . De lo contrario, escriba “No” .
Una subsecuencia no contigua contiene al menos dos caracteres consecutivos de índices no consecutivos.
Ejemplos:
Entrada: arr[] = {1, 7, 12, 1, 7, 5, 10, 11, 42}, L = 3, R = 6
Salida: Sí
Explicación: La subsecuencia no contigua {arr[0], arr [1], arr[5], arr[6]} es lo mismo que el subarreglo {arr[3], .., arr[6]}.Entrada: arr[] = {0, 1, 2, -2, 5, 10}, L = 1, R = 3
Enfoque ingenuo: el enfoque más simple es generar todas las subsecuencias posibles de la array dada y verificar si alguna de las subsecuencias generadas es igual o no a la subarreglo dado. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Complejidad temporal: O(N*2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea se basa en la observación clave de que siempre habrá una subsecuencia no contigua si hay al menos una ocurrencia del primer elemento del subarreglo dado en el rango [0, L – 1] y al menos una ocurrencia del último elemento de un subarreglo en el rango [R + 1, N] .
Prueba de lógica:
Si el primer elemento del subarreglo { arr[L], … arr[R]} también ocurre en cualquier índice K (K < L), entonces una de esas subsecuencias no contiguas puede ser {arr[K], arr[L + 1], …., arr[R]} .
Si el último elemento del subarreglo {arr[L], … arr[R]} también ocurre en cualquier índice K (K > R), entonces una de esas subsecuencias no contiguas puede ser strong>{arr[L], arr[ L + 1], …., arr[R – 1], arr[K]}.
Si no se cumple ninguna de las dos condiciones anteriores, entonces no existe tal subsecuencia no contigua.
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;
// Utility Function to check whether
// a subsequence same as the given
// subarray exists or not
bool checkSubsequenceUtil(
int arr[], int L, int R, int N)
{
// Check if first element of the
// subarray is also present before
for (int i = 0; i < L; i++)
if (arr[i] == arr[L])
return true;
// Check if last element of the
// subarray is also present later
for (int i = R + 1; i < N; i++)
if (arr[i] == arr[R])
return true;
// If above two conditions are
// not satisfied, then no such
// subsequence exists
return false;
}
// Function to check and print if a
// subsequence which is same as the
// given subarray is present or not
void checkSubsequence(int arr[], int L,
int R, int N)
{
if (checkSubsequenceUtil(arr, L,
R, N)) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
// Driver Code
int main()
{
int arr[] = { 1, 7, 12, 1, 7,
5, 10, 11, 42 };
int N = sizeof(arr) / sizeof(arr[0]);
int L = 3, R = 6;
// Function Call
checkSubsequence(arr, L, R, N);
}
Java
// Java program for the above approach
class GFG{
// Utility Function to check whether
// a subsequence same as the given
// subarray exists or not
static boolean checkSubsequenceUtil(int arr[], int L,
int R, int N)
{
// Check if first element of the
// subarray is also present before
for(int i = 0; i < L; i++)
if (arr[i] == arr[L])
return true;
// Check if last element of the
// subarray is also present later
for(int i = R + 1; i < N; i++)
if (arr[i] == arr[R])
return true;
// If above two conditions are
// not satisfied, then no such
// subsequence exists
return false;
}
// Function to check and print if a
// subsequence which is same as the
// given subarray is present or not
static void checkSubsequence(int arr[], int L,
int R, int N)
{
if (checkSubsequenceUtil(arr, L,
R, N))
{
System.out.print("YES\n");
}
else
{
System.out.print("NO\n");
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 7, 12, 1, 7,
5, 10, 11, 42 };
int N = arr.length;
int L = 3, R = 6;
// Function Call
checkSubsequence(arr, L, R, N);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach
# Utility Function to check whether
# a subsequence same as the given
# subarray exists or not
def checkSubsequenceUtil(arr, L, R, N):
# Check if first element of the
# subarray is also present before
for i in range(L):
if (arr[i] == arr[L]):
return True
# Check if last element of the
# subarray is also present later
for i in range(R + 1, N, 1):
if (arr[i] == arr[R]):
return True
# If above two conditions are
# not satisfied, then no such
# subsequence exists
return False
# Function to check and print if a
# subsequence which is same as the
# given subarray is present or not
def checkSubsequence(arr, L, R, N):
if (checkSubsequenceUtil(arr, L,R, N)):
print("YES")
else:
print("NO")
# Driver Code
arr = [ 1, 7, 12, 1, 7,
5, 10, 11, 42 ]
N = len(arr)
L = 3
R = 6
# Function Call
checkSubsequence(arr, L, R, N)
# This code is contributed by susmitakundugoaldanga
C#
// C# program for the above approach
using System;
class GFG{
// Utility Function to check whether
// a subsequence same as the given
// subarray exists or not
static bool checkSubsequenceUtil(int[] arr, int L,
int R, int N)
{
// Check if first element of the
// subarray is also present before
for(int i = 0; i < L; i++)
if (arr[i] == arr[L])
return true;
// Check if last element of the
// subarray is also present later
for(int i = R + 1; i < N; i++)
if (arr[i] == arr[R])
return true;
// If above two conditions are
// not satisfied, then no such
// subsequence exists
return false;
}
// Function to check and print if a
// subsequence which is same as the
// given subarray is present or not
static void checkSubsequence(int[] arr, int L,
int R, int N)
{
if (checkSubsequenceUtil(arr, L,
R, N))
{
Console.Write("YES\n");
}
else
{
Console.Write("NO\n");
}
}
// Driver code
public static void Main()
{
int[] arr = { 1, 7, 12, 1, 7,
5, 10, 11, 42 };
int N = arr.Length;
int L = 3, R = 6;
// Function Call
checkSubsequence(arr, L, R, N);
}
}
// This code is contributed by code_hunt
Javascript
<script>
// javascript program to implement
// the above approach
// Utility Function to check whether
// a subsequence same as the given
// subarray exists or not
function checkSubsequenceUtil(arr, L,
R, N)
{
// Check if first element of the
// subarray is also present before
for(let i = 0; i < L; i++)
if (arr[i] == arr[L])
return true;
// Check if last element of the
// subarray is also present later
for(let i = R + 1; i < N; i++)
if (arr[i] == arr[R])
return true;
// If above two conditions are
// not satisfied, then no such
// subsequence exists
return false;
}
// Function to check and print if a
// subsequence which is same as the
// given subarray is present or not
function checkSubsequence(arr, L,
R, N)
{
if (checkSubsequenceUtil(arr, L,
R, N))
{
document.write("YES\n");
}
else
{
document.write("NO\n");
}
}
// Driver code
let arr = [ 1, 7, 12, 1, 7,
5, 10, 11, 42 ];
let N = arr.length;
let L = 3, R = 6;
// Function Call
checkSubsequence(arr, L, R, N);
// This code is contributed by souravghosh0416.
</script>
YES
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shekabhi1208 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA