Dada una array arr[] que consiste en una permutación de números en el rango [0, N – 1] , la tarea es encontrar la longitud del subconjunto más largo de la array tal que los elementos en el subconjunto tengan la forma { arr [i], arr[arr[i]], arr[arr[arr[i]]], …}
Ejemplos:
Entrada: arr[] = {5, 4, 0, 3, 1, 6, 2}
Salida: 4
Explicación:
arr[arr[0]] es igual a arr[5]
arr[arr[arr[0]]] es igual a arr[6]
arr[arr[arr[arr[0]]]] es igual a arr[2]
Uno de los posibles subconjuntos de la array es {arr[0], arr[5], arr[6 ], arr[2]} = {5, 6, 2, 0}, que es el subconjunto más largo que satisface la condición dada. Por lo tanto, la salida requerida es 4.Entrada: arr[] ={3, 1, 4, 0, 2}
Salida: 2
Explicación:
arr[arr[0]] es igual a arr[3]
Uno de los posibles subconjuntos de la array es {arr[0] , arr[3]} = {3, 0}
Por lo tanto, la salida requerida es 2.
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una variable res = 0 para almacenar la longitud del subconjunto más largo de la array que cumple la condición.
- Recorra la array arr[] y realice las siguientes operaciones:
- Compruebe si arr[i] es igual a i o no. Si se determina que es cierto, actualice res = max(res, 1) .
- Inicialice una variable, digamos index = i , para almacenar el índice de elementos de un subconjunto de la array dada.
- Iterar sobre elementos de un subconjunto mientras arr[index] != index , actualizar el elemento actual del subconjunto al índice actual y también actualizar index = arr[index] .
- Finalmente, actualice el res al máximo de res y el recuento de elementos en el subconjunto actual.
- Finalmente, imprima el res .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find length of longest subset
// such that subset { arr[i], arr[arr[i]], .. }
int arrayNesting(vector<int> arr)
{
// Stores length of the longest subset
// that satisfy the condition
int res = 0;
// Traverse in the array, arr[]
for (int i = 0; i < arr.size(); i++)
{
// If arr[i] equals to i
if (arr[i] == i)
{
// Update res
res = max(res, 1);
}
else
{
// Count of elements in a subset
int count = 0;
// Stores index of elements in
// the current subset
int curr_index = i;
// Calculate length of a subset that
// satisfy the condition
while (arr[curr_index] != curr_index)
{
int next_index = arr[curr_index];
// Make visited the current index
arr[curr_index] = curr_index;
// Update curr_index
curr_index = next_index;
// Update count
count++;
}
// Update res
res = max(res, count);
}
}
return res;
}
// Driver Code
int main()
{
vector<int> arr = { 5, 4, 0, 3, 1, 6, 2 };
int res = arrayNesting(arr);
cout<<res;
}
// This code is contributed by mohit kumar 29.
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class sol {
// Function to find length of longest subset
// such that subset { arr[i], arr[arr[i]], .. }
public int arrayNesting(int[] arr)
{
// Stores length of the longest subset
// that satisfy the condition
int res = 0;
// Traverse in the array, arr[]
for (int i = 0; i < arr.length; i++) {
// If arr[i] equals to i
if (arr[i] == i) {
// Update res
res = Math.max(res, 1);
}
else {
// Count of elements in a subset
int count = 0;
// Stores index of elements in
// the current subset
int curr_index = i;
// Calculate length of a subset that
// satisfy the condition
while (arr[curr_index]
!= curr_index) {
int next_index = arr[curr_index];
// Make visited the current index
arr[curr_index] = curr_index;
// Update curr_index
curr_index = next_index;
// Update count
count++;
}
// Update res
res = Math.max(res, count);
}
}
return res;
}
}
// Driver Code
class GFG {
public static void main(String[] args)
{
sol st = new sol();
int[] arr = { 5, 4, 0, 3, 1, 6, 2 };
int res = st.arrayNesting(arr);
System.out.println(res);
}
}
C#
// C# program to implement
// the above approach
using System;
class sol {
// Function to find length of longest subset
// such that subset { arr[i], arr[arr[i]], .. }
public int arrayNesting(int[] arr)
{
// Stores length of the longest subset
// that satisfy the condition
int res = 0;
// Traverse in the array, arr[]
for (int i = 0; i < arr.Length; i++) {
// If arr[i] equals to i
if (arr[i] == i) {
// Update res
res = Math.Max(res, 1);
}
else {
// Count of elements in a subset
int count = 0;
// Stores index of elements in
// the current subset
int curr_index = i;
// Calculate length of a subset that
// satisfy the condition
while (arr[curr_index] != curr_index) {
int next_index = arr[curr_index];
// Make visited the current index
arr[curr_index] = curr_index;
// Update curr_index
curr_index = next_index;
// Update count
count++;
}
// Update res
res = Math.Max(res, count);
}
}
return res;
}
}
// Driver Code
class GFG {
static public void Main()
{
sol st = new sol();
int[] arr = { 5, 4, 0, 3, 1, 6, 2 };
int res = st.arrayNesting(arr);
Console.WriteLine(res);
}
}
// This code is contributed by Dharanendra L V
Python3
# Python program for the above approach
# Function to find length of longest subset
# such that subset { arr[i], arr[arr[i]], .. }
def arrayNesting(arr) :
# Stores length of the longest subset
# that satisfy the condition
res = 0
# Traverse in the array, arr[]
for i in range(len(arr)) :
# If arr[i] equals to i
if arr[i] == i :
# Update res
res = max(res, 1)
else :
# Count of elements in a subset
count = 0
# Stores index of elements in
# the current subset
curr_index = i
# Calculate length of a subset that
# satisfy the condition
while arr[curr_index] != curr_index :
next_index = arr[curr_index]
# Make visited the current index
arr[curr_index] = curr_index
# Update curr_index
curr_index = next_index
# Update count
count += 1
# Update res
res = max(res, count)
return res
# Driver Code
if __name__ == "__main__" :
arr = [ 5, 4, 0, 3, 1, 6, 2 ]
res = arrayNesting(arr)
print(res)
# This code is contributed by jana_sayantam..
Javascript
<script>
// javascript program of the above approach
// Function to find length of longest subset
// such that subset { arr[i], arr[arr[i]], .. }
function arrayNesting(arr)
{
// Stores length of the longest subset
// that satisfy the condition
let res = 0;
// Traverse in the array, arr[]
for (let i = 0; i < arr.length; i++) {
// If arr[i] equals to i
if (arr[i] == i) {
// Update res
res = Math.max(res, 1);
}
else {
// Count of elements in a subset
let count = 0;
// Stores index of elements in
// the current subset
let curr_index = i;
// Calculate length of a subset that
// satisfy the condition
while (arr[curr_index]
!= curr_index) {
let next_index = arr[curr_index];
// Make visited the current index
arr[curr_index] = curr_index;
// Update curr_index
curr_index = next_index;
// Update count
count++;
}
// Update res
res = Math.max(res, count);
}
}
return res;
}
// Driver Code
let arr = [ 5, 4, 0, 3, 1, 6, 2 ];
let res = arrayNesting(arr);
document.write(res);
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA