Número de subsecuencias crecientes más largas

Posted on by Rudeus Greyrat

Dada una array arr[] de tamaño N , la tarea es contar el número de subsecuencias crecientes más largas presentes en la array dada.

Ejemplos:

Entrada: arr[] = {2, 2, 2, 2, 2}
Salida: 5
Explicación: La longitud de la subsecuencia creciente más larga es 1, es decir, {2}. Por lo tanto, el recuento de subsecuencias crecientes más largas de longitud 1 es 5.

Entrada: arr[] = {1, 3, 5, 4, 7}
Salida: 2
Explicación: La longitud de la subsecuencia creciente más larga es 4, y hay 2 subsecuencias crecientes más largas de longitud 4, es decir, {1, 3, 4 , 7} y {1, 3, 5, 7}.

Enfoque ingenuo: el enfoque más simple es generar todas las subsecuencias posibles presentes en la array dada arr[] y contar las subsecuencias crecientes de longitud máxima. Imprime el conteo después de verificar todas las subsecuencias. 

Complejidad temporal: O(N*2 N )
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la programación dinámica , ya que el problema anterior tiene subproblemas superpuestos que deben calcularse más de una vez, y para reducir ese cálculo, use la tabulación o la memorización . Siga los pasos a continuación para resolver el problema:

  • Inicialice dos arrays dp_l[] y dp_c[] para almacenar la longitud de las subsecuencias crecientes más largas y el recuento de la subsecuencia creciente más larga en cada índice, respectivamente.
  • Iterar sobre el rango [1, N – 1] usando la variable i :
    • Iterar sobre el rango [0, i – 1] usando la variable j :
      • Si arr[i] > arr[j] , compruebe los siguientes casos:
                ~ Si ( dp_l[j]+1) es mayor que dp_l[i] , actualice dp_l[i] como dp_l[j] + 1 y dp_c[ i] como dp_c[j]
                ~ De lo contrario, si (dp_l[j] + 1) es lo mismo que dp_l[i] , actualice dp_c[i] como dp_c[i] + dp_c[j] .
  • Encuentre el elemento máximo en la array dp_l[] y guárdelo en una variable max_length que le dará la longitud de LIS.
  • Inicialice una cuenta variable con 0 para almacenar el número de la subsecuencia creciente más larga.
  • Recorra la array dp_l[] y, si en cualquier índice idx , dp_l[idx] es lo mismo que max_length , incremente el conteo en dp_c[idx] .
  • Después de los pasos anteriores, imprima el valor de count , que es el número de subsecuencias crecientes más largas en la array dada.

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 count the number
// of LIS in the array nums[]
int findNumberOfLIS(vector<int> nums)
{
  //Base Case
  if (nums.size() == 0)
    return 0;
 
  int n = nums.size();
 
  //Initialize dp_l array with
  // 1s
  vector<int> dp_l(n, 1);
 
  //Initialize dp_c array with
  // 1s
  vector<int> dp_c(n, 1);
 
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < i; j++)
    {
      //If current element is
      // smaller
      if (nums[i] <= nums[j])
        continue;
 
      if  (dp_l[j] + 1 > dp_l[i])
      {
        dp_l[i] = dp_l[j] + 1;
        dp_c[i] = dp_c[j];
      }
      else if (dp_l[j] + 1 == dp_l[i])
        dp_c[i] += dp_c[j];
    }
  }
 
  //Store the maximum element
  // from dp_l
  int max_length = 0;
 
  for (int i : dp_l)
    max_length = max(i,max_length);
 
  //Stores the count of LIS
  int count = 0;
 
  //Traverse dp_l and dp_c
  // simultaneously
  for(int i = 0; i < n; i++)
  {
    //Update the count
    if (dp_l[i] == max_length)
      count += dp_c[i];
  }
   
  //Return the count of LIS
  return count;
}
 
//Driver code
int main()
{
  //Given array arr[]
  vector<int> arr = {1, 3, 5, 4, 7};
 
  //Function Call
  cout << findNumberOfLIS(arr) << endl;
}
 
// This code is contributed by Mohit Kumar 29

Java

// Java program for the
// above approach
import java.util.*;
 
class GFG{
 
// Function to count the number
// of LIS in the array nums[]
static int findNumberOfLIS(int[] nums)
{
   
  // Base Case
  if (nums.length == 0)
      return 0;
   
  int n = nums.length;
   
  // Initialize dp_l array with
  // 1s
  int[] dp_l = new int[n];
  Arrays.fill(dp_l, 1);
 
  // Initialize dp_c array with
  // 1s
  int[] dp_c = new int[n];
  Arrays.fill(dp_c, 1);
 
  for(int i = 0; i < n; i++)
  {
    for(int j = 0; j < i; j++)
    {
       
      // If current element is
      // smaller
      if (nums[i] <= nums[j])
        continue;
 
      if (dp_l[j] + 1 > dp_l[i])
      {
        dp_l[i] = dp_l[j] + 1;
        dp_c[i] = dp_c[j];
      }
      else if (dp_l[j] + 1 == dp_l[i])
        dp_c[i] += dp_c[j];
    }
  }
 
  // Store the maximum element
  // from dp_l
  int max_length = 0;
 
  for(int i : dp_l)
    max_length = Math.max(i, max_length);
 
  // Stores the count of LIS
  int count = 0;
 
  // Traverse dp_l and dp_c
  // simultaneously
  for(int i = 0; i < n; i++)
  {
     
    // Update the count
    if (dp_l[i] == max_length)
      count += dp_c[i];
  }
   
  // Return the count of LIS
  return count;
}
 
// Driver code
public static void main(String[] args)
{
   
  // Given array arr[]
  int[] arr = { 1, 3, 5, 4, 7 };
 
  // Function Call
  System.out.print(findNumberOfLIS(arr) + "\n");
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 program for the above approach
 
# Function to count the number of LIS
# in the array nums[]
def findNumberOfLIS(nums):
 
    # Base Case
    if not nums:
        return 0
 
    n = len(nums)
 
    # Initialize dp_l array with 1s
    dp_l = [1] * n
 
    # Initialize dp_c array with 1s
    dp_c = [1] * n
 
    for i, num in enumerate(nums):
        for j in range(i):
 
            # If current element is smaller
            if nums[i] <= nums[j]:
                continue
 
            # Otherwise
            if dp_l[j] + 1 > dp_l[i]:
                dp_l[i] = dp_l[j] + 1
                dp_c[i] = dp_c[j]
 
            elif dp_l[j] + 1 == dp_l[i]:
                dp_c[i] += dp_c[j]
 
    # Store the maximum element from dp_l
    max_length = max(x for x in dp_l)
 
    # Stores the count of LIS
    count = 0
 
    # Traverse dp_l and dp_c simultaneously
    for l, c in zip(dp_l, dp_c):
 
        # Update the count
        if l == max_length:
            count += c
 
    # Return the count of LIS
    return count
 
# Driver Code
 
# Given array arr[]
arr = [1, 3, 5, 4, 7]
 
# Function Call
print(findNumberOfLIS(arr))

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG {
     
    // Function to count the number
    // of LIS in the array nums[]
    static int findNumberOfLIS(int[] nums)
    {
        
      // Base Case
      if (nums.Length == 0)
          return 0;
        
      int n = nums.Length;
        
      // Initialize dp_l array with
      // 1s
      int[] dp_l = new int[n];
      Array.Fill(dp_l, 1);
      
      // Initialize dp_c array with
      // 1s
      int[] dp_c = new int[n];
      Array.Fill(dp_c, 1);
      
      for(int i = 0; i < n; i++)
      {
        for(int j = 0; j < i; j++)
        {
            
          // If current element is
          // smaller
          if (nums[i] <= nums[j])
            continue;
      
          if (dp_l[j] + 1 > dp_l[i])
          {
            dp_l[i] = dp_l[j] + 1;
            dp_c[i] = dp_c[j];
          }
          else if (dp_l[j] + 1 == dp_l[i])
            dp_c[i] += dp_c[j];
        }
      }
      
      // Store the maximum element
      // from dp_l
      int max_length = 0;
      
      foreach(int i in dp_l)
        max_length = Math.Max(i, max_length);
      
      // Stores the count of LIS
      int count = 0;
      
      // Traverse dp_l and dp_c
      // simultaneously
      for(int i = 0; i < n; i++)
      {
          
        // Update the count
        if (dp_l[i] == max_length)
          count += dp_c[i];
      }
        
      // Return the count of LIS
      return count;
    }
 
  // Driver code
  static void Main() {
       
      // Given array arr[]
      int[] arr = { 1, 3, 5, 4, 7 };
      
      // Function Call
      Console.WriteLine(findNumberOfLIS(arr));
  }
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
 
// Javascript program for the
// above approach
 
// Function to count the number
// of LIS in the array nums[]
function findNumberOfLIS(nums)
{
  //Base Case
  if (nums.length == 0)
    return 0;
 
  var n = nums.length;
 
  // Initialize dp_l array with
  // 1s
  var dp_l = Array(n).fill(1);
 
  // Initialize dp_c array with
  // 1s
  var dp_c = Array(n).fill(1);
 
  for (var i = 0; i < n; i++)
  {
    for (var j = 0; j < i; j++)
    {
      // If current element is
      // smaller
      if (nums[i] <= nums[j])
        continue;
 
      if  (dp_l[j] + 1 > dp_l[i])
      {
        dp_l[i] = dp_l[j] + 1;
        dp_c[i] = dp_c[j];
      }
      else if (dp_l[j] + 1 == dp_l[i])
        dp_c[i] += dp_c[j];
    }
  }
 
  // Store the maximum element
  // from dp_l
  var max_length = 0;
 
  dp_l.forEach(i => {
       
    max_length = Math.max(i,max_length);
  });
 
  // Stores the count of LIS
  var count = 0;
 
  //Traverse dp_l and dp_c
  // simultaneously
  for(var i = 0; i < n; i++)
  {
    // Update the count
    if (dp_l[i] == max_length)
      count += dp_c[i];
  }
   
  // Return the count of LIS
  return count;
}
 
// Driver code
// Given array arr[]
var arr = [1, 3, 5, 4, 7];
 
// Function Call
document.write( findNumberOfLIS(arr));
 
// This code is contributed by rutvik_56.
</script>
Producción: 

2

 

Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por saikumarkudikala 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 *