Subconjunto más largo de elementos anidados de una array dada

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:
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:
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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *