Subsecuencia más larga tal que la diferencia entre adyacentes sea uno
Pruébalo en GfG Practice 
Producción
Producción
Producción
dado un a arreglo de matriz[] de talla n la tarea es encontrar el subsecuencia más larga tal que el diferencia absoluta entre elementos adyacentes es 1.
Ejemplos:
Aporte: arreglo[] = [10 9 4 5 4 8 6]
Producción: 3
Explicación: Las tres posibles subsecuencias de longitud 3 son [10 9 8] [4 5 4] y [4 5 6] donde los elementos adyacentes tienen una diferencia absoluta de 1. No se pudo formar ninguna subsecuencia válida de mayor longitud.
Aporte: arreglo[] = [1 2 3 4 5]
Producción: 5
Explicación: Todos los elementos pueden incluirse en la subsecuencia válida.
Uso de la recursividad: tiempo O(2^n) y espacio O(n)
C++Para el enfoque recursivo consideraremos dos casos en cada paso:
- Si el elemento satisface la condición (el diferencia absoluta entre elementos adyacentes es 1) nosotros incluir en la subsecuencia y pasar a la próximo elemento.
- más nosotros saltar el actual elemento y pasar al siguiente.
Matemáticamente el relación de recurrencia se verá así:
- lowerSubseq(arr idx prev) = max(longestSubseq(arr idx + 1 prev) 1 + longSubseq(arr idx + 1 idx))
Caso base:
- Cuando idx == arreglo.tamaño() tenemos alcanzó el final de la matriz así regresar 0 (ya que no se pueden incluir más elementos).
// C++ program to find the longest subsequence such that // the difference between adjacent elements is one using // recursion. #include using namespace std ; int subseqHelper ( int idx int prev vector < int >& arr ) { // Base case: if index reaches the end of the array if ( idx == arr . size ()) { return 0 ; } // Skip the current element and move to the next index int noTake = subseqHelper ( idx + 1 prev arr ); // Take the current element if the condition is met int take = 0 ; if ( prev == -1 || abs ( arr [ idx ] - arr [ prev ]) == 1 ) { take = 1 + subseqHelper ( idx + 1 idx arr ); } // Return the maximum of the two options return max ( take noTake ); } // Function to find the longest subsequence int longestSubseq ( vector < int >& arr ) { // Start recursion from index 0 // with no previous element return subseqHelper ( 0 -1 arr ); } int main () { vector < int > arr = { 10 9 4 5 4 8 6 }; cout < < longestSubseq ( arr ); return 0 ; }
Java // Java program to find the longest subsequence such that // the difference between adjacent elements is one using // recursion. import java.util.ArrayList ; class GfG { // Helper function to recursively find the subsequence static int subseqHelper ( int idx int prev ArrayList < Integer > arr ) { // Base case: if index reaches the end of the array if ( idx == arr . size ()) { return 0 ; } // Skip the current element and move to the next index int noTake = subseqHelper ( idx + 1 prev arr ); // Take the current element if the condition is met int take = 0 ; if ( prev == - 1 || Math . abs ( arr . get ( idx ) - arr . get ( prev )) == 1 ) { take = 1 + subseqHelper ( idx + 1 idx arr ); } // Return the maximum of the two options return Math . max ( take noTake ); } // Function to find the longest subsequence static int longestSubseq ( ArrayList < Integer > arr ) { // Start recursion from index 0 // with no previous element return subseqHelper ( 0 - 1 arr ); } public static void main ( String [] args ) { ArrayList < Integer > arr = new ArrayList <> (); arr . add ( 10 ); arr . add ( 9 ); arr . add ( 4 ); arr . add ( 5 ); arr . add ( 4 ); arr . add ( 8 ); arr . add ( 6 ); System . out . println ( longestSubseq ( arr )); } }
Python # Python program to find the longest subsequence such that # the difference between adjacent elements is one using # recursion. def subseq_helper ( idx prev arr ): # Base case: if index reaches the end of the array if idx == len ( arr ): return 0 # Skip the current element and move to the next index no_take = subseq_helper ( idx + 1 prev arr ) # Take the current element if the condition is met take = 0 if prev == - 1 or abs ( arr [ idx ] - arr [ prev ]) == 1 : take = 1 + subseq_helper ( idx + 1 idx arr ) # Return the maximum of the two options return max ( take no_take ) def longest_subseq ( arr ): # Start recursion from index 0 # with no previous element return subseq_helper ( 0 - 1 arr ) if __name__ == '__main__' : arr = [ 10 9 4 5 4 8 6 ] print ( longest_subseq ( arr ))
C# // C# program to find the longest subsequence such that // the difference between adjacent elements is one using // recursion. using System ; using System.Collections.Generic ; class GfG { // Helper function to recursively find the subsequence static int SubseqHelper ( int idx int prev List < int > arr ) { // Base case: if index reaches the end of the array if ( idx == arr . Count ) { return 0 ; } // Skip the current element and move to the next index int noTake = SubseqHelper ( idx + 1 prev arr ); // Take the current element if the condition is met int take = 0 ; if ( prev == - 1 || Math . Abs ( arr [ idx ] - arr [ prev ]) == 1 ) { take = 1 + SubseqHelper ( idx + 1 idx arr ); } // Return the maximum of the two options return Math . Max ( take noTake ); } // Function to find the longest subsequence static int LongestSubseq ( List < int > arr ) { // Start recursion from index 0 // with no previous element return SubseqHelper ( 0 - 1 arr ); } static void Main ( string [] args ) { List < int > arr = new List < int > { 10 9 4 5 4 8 6 }; Console . WriteLine ( LongestSubseq ( arr )); } }
JavaScript // JavaScript program to find the longest subsequence // such that the difference between adjacent elements // is one using recursion. function subseqHelper ( idx prev arr ) { // Base case: if index reaches the end of the array if ( idx === arr . length ) { return 0 ; } // Skip the current element and move to the next index let noTake = subseqHelper ( idx + 1 prev arr ); // Take the current element if the condition is met let take = 0 ; if ( prev === - 1 || Math . abs ( arr [ idx ] - arr [ prev ]) === 1 ) { take = 1 + subseqHelper ( idx + 1 idx arr ); } // Return the maximum of the two options return Math . max ( take noTake ); } function longestSubseq ( arr ) { // Start recursion from index 0 // with no previous element return subseqHelper ( 0 - 1 arr ); } const arr = [ 10 9 4 5 4 8 6 ]; console . log ( longestSubseq ( arr ));
Producción
3
Uso de DP de arriba hacia abajo (memorización ) - O(n^2) tiempo y O(n^2) Espacio
Si observamos con atención, podemos observar que la solución recursiva anterior tiene las siguientes dos propiedades de Programación dinámica :
1. Subestructura óptima: La solución para encontrar la subsecuencia más larga tal que la diferencia entre elementos adyacentes se puede derivar la solución óptima de subproblemas más pequeños. Específicamente para cualquier identificación (índice actual) y anterior (índice anterior en la subsecuencia) podemos expresar la relación recursiva de la siguiente manera:
- subseqHelper(idx anterior) = max(subseqHelper(idx + 1 anterior) 1 + subseqHelper(idx + 1 idx))
2. Subproblemas superpuestos: Al implementar un recursivo enfoque para resolver el problema observamos que muchos subproblemas se calculan varias veces. Por ejemplo al calcular subseqAyudante(0 -1) para una matriz llegada = [10 9 4 5] el subproblema subseqAyudante(2 -1) puede ser calculado múltiple veces. Para evitar esta repetición utilizamos la memorización para almacenar los resultados de subproblemas previamente calculados.
La solución recursiva implica dos parámetros:
- identificación (el índice actual en la matriz).
- anterior (el índice del último elemento incluido en la subsecuencia).
Necesitamos rastrear ambos parametros entonces creamos un nota de matriz 2D de tamaño (n) x (n+1) . Inicializamos el Nota de matriz 2D con -1 para indicar que aún no se han calculado subproblemas. Antes de calcular un resultado comprobamos si el valor en nota[idx][anterior+1] es -1. Si es así, calculamos y almacenar el resultado. De lo contrario devolvemos el resultado almacenado.
C++ // C++ program to find the longest subsequence such that // the difference between adjacent elements is one using // recursion with memoization. #include using namespace std ; // Helper function to recursively find the subsequence int subseqHelper ( int idx int prev vector < int >& arr vector < vector < int >>& memo ) { // Base case: if index reaches the end of the array if ( idx == arr . size ()) { return 0 ; } // Check if the result is already computed if ( memo [ idx ][ prev + 1 ] != -1 ) { return memo [ idx ][ prev + 1 ]; } // Skip the current element and move to the next index int noTake = subseqHelper ( idx + 1 prev arr memo ); // Take the current element if the condition is met int take = 0 ; if ( prev == -1 || abs ( arr [ idx ] - arr [ prev ]) == 1 ) { take = 1 + subseqHelper ( idx + 1 idx arr memo ); } // Store the result in the memo table return memo [ idx ][ prev + 1 ] = max ( take noTake ); } // Function to find the longest subsequence int longestSubseq ( vector < int >& arr ) { int n = arr . size (); // Create a memoization table initialized to -1 vector < vector < int >> memo ( n vector < int > ( n + 1 -1 )); // Start recursion from index 0 with no previous element return subseqHelper ( 0 -1 arr memo ); } int main () { // Input array of integers vector < int > arr = { 10 9 4 5 4 8 6 }; cout < < longestSubseq ( arr ); return 0 ; }
Java // Java program to find the longest subsequence such that // the difference between adjacent elements is one using // recursion with memoization. import java.util.ArrayList ; import java.util.Arrays ; class GfG { // Helper function to recursively find the subsequence static int subseqHelper ( int idx int prev ArrayList < Integer > arr int [][] memo ) { // Base case: if index reaches the end of the array if ( idx == arr . size ()) { return 0 ; } // Check if the result is already computed if ( memo [ idx ][ prev + 1 ] != - 1 ) { return memo [ idx ][ prev + 1 ] ; } // Skip the current element and move to the next index int noTake = subseqHelper ( idx + 1 prev arr memo ); // Take the current element if the condition is met int take = 0 ; if ( prev == - 1 || Math . abs ( arr . get ( idx ) - arr . get ( prev )) == 1 ) { take = 1 + subseqHelper ( idx + 1 idx arr memo ); } // Store the result in the memo table memo [ idx ][ prev + 1 ] = Math . max ( take noTake ); // Return the stored result return memo [ idx ][ prev + 1 ] ; } // Function to find the longest subsequence static int longestSubseq ( ArrayList < Integer > arr ) { int n = arr . size (); // Create a memoization table initialized to -1 int [][] memo = new int [ n ][ n + 1 ] ; for ( int [] row : memo ) { Arrays . fill ( row - 1 ); } // Start recursion from index 0 // with no previous element return subseqHelper ( 0 - 1 arr memo ); } public static void main ( String [] args ) { ArrayList < Integer > arr = new ArrayList <> (); arr . add ( 10 ); arr . add ( 9 ); arr . add ( 4 ); arr . add ( 5 ); arr . add ( 4 ); arr . add ( 8 ); arr . add ( 6 ); System . out . println ( longestSubseq ( arr )); } }
Python # Python program to find the longest subsequence such that # the difference between adjacent elements is one using # recursion with memoization. def subseq_helper ( idx prev arr memo ): # Base case: if index reaches the end of the array if idx == len ( arr ): return 0 # Check if the result is already computed if memo [ idx ][ prev + 1 ] != - 1 : return memo [ idx ][ prev + 1 ] # Skip the current element and move to the next index no_take = subseq_helper ( idx + 1 prev arr memo ) # Take the current element if the condition is met take = 0 if prev == - 1 or abs ( arr [ idx ] - arr [ prev ]) == 1 : take = 1 + subseq_helper ( idx + 1 idx arr memo ) # Store the result in the memo table memo [ idx ][ prev + 1 ] = max ( take no_take ) # Return the stored result return memo [ idx ][ prev + 1 ] def longest_subseq ( arr ): n = len ( arr ) # Create a memoization table initialized to -1 memo = [[ - 1 for _ in range ( n + 1 )] for _ in range ( n )] # Start recursion from index 0 with # no previous element return subseq_helper ( 0 - 1 arr memo ) if __name__ == '__main__' : arr = [ 10 9 4 5 4 8 6 ] print ( longest_subseq ( arr ))
C# // C# program to find the longest subsequence such that // the difference between adjacent elements is one using // recursion with memoization. using System ; using System.Collections.Generic ; class GfG { // Helper function to recursively find the subsequence static int SubseqHelper ( int idx int prev List < int > arr int [] memo ) { // Base case: if index reaches the end of the array if ( idx == arr . Count ) { return 0 ; } // Check if the result is already computed if ( memo [ idx prev + 1 ] != - 1 ) { return memo [ idx prev + 1 ]; } // Skip the current element and move to the next index int noTake = SubseqHelper ( idx + 1 prev arr memo ); // Take the current element if the condition is met int take = 0 ; if ( prev == - 1 || Math . Abs ( arr [ idx ] - arr [ prev ]) == 1 ) { take = 1 + SubseqHelper ( idx + 1 idx arr memo ); } // Store the result in the memoization table memo [ idx prev + 1 ] = Math . Max ( take noTake ); // Return the stored result return memo [ idx prev + 1 ]; } // Function to find the longest subsequence static int LongestSubseq ( List < int > arr ) { int n = arr . Count ; // Create a memoization table initialized to -1 int [] memo = new int [ n n + 1 ]; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j <= n ; j ++ ) { memo [ i j ] = - 1 ; } } // Start recursion from index 0 with no previous element return SubseqHelper ( 0 - 1 arr memo ); } static void Main ( string [] args ) { List < int > arr = new List < int > { 10 9 4 5 4 8 6 }; Console . WriteLine ( LongestSubseq ( arr )); } }
JavaScript // JavaScript program to find the longest subsequence // such that the difference between adjacent elements // is one using recursion with memoization. function subseqHelper ( idx prev arr memo ) { // Base case: if index reaches the end of the array if ( idx === arr . length ) { return 0 ; } // Check if the result is already computed if ( memo [ idx ][ prev + 1 ] !== - 1 ) { return memo [ idx ][ prev + 1 ]; } // Skip the current element and move to the next index let noTake = subseqHelper ( idx + 1 prev arr memo ); // Take the current element if the condition is met let take = 0 ; if ( prev === - 1 || Math . abs ( arr [ idx ] - arr [ prev ]) === 1 ) { take = 1 + subseqHelper ( idx + 1 idx arr memo ); } // Store the result in the memoization table memo [ idx ][ prev + 1 ] = Math . max ( take noTake ); // Return the stored result return memo [ idx ][ prev + 1 ]; } function longestSubseq ( arr ) { let n = arr . length ; // Create a memoization table initialized to -1 let memo = Array . from ({ length : n } () => Array ( n + 1 ). fill ( - 1 )); // Start recursion from index 0 with no previous element return subseqHelper ( 0 - 1 arr memo ); } const arr = [ 10 9 4 5 4 8 6 ]; console . log ( longestSubseq ( arr ));
Producción
3
Uso de DP ascendente (tabulación) - En) tiempo y En) Espacio
El enfoque es similar al recursivo método, pero en lugar de dividir el problema de forma recursiva, construimos iterativamente la solución en un manera ascendente.
En lugar de utilizar la recursividad utilizamos un mapa hash tabla de programación dinámica basada (dp) para almacenar el longitudes de las subsecuencias más largas. Esto nos ayuda a calcular y actualizar eficientemente el subsecuencia longitudes para todos los valores posibles de los elementos de la matriz.
C++Relación de programación dinámica:
dp[x] representa el longitud de la subsecuencia más larga que termina con el elemento x.
Para cada elemento llegar[yo] en la matriz: si llegada[i] + 1 o arreglo[i] - 1 existe en dp:
- dp[arr[i]] = 1 + máx(dp[arr[i] + 1] dp[arr[i] - 1]);
Esto significa que podemos extender las subsecuencias que terminan en llegada[i] + 1 o arreglo[i] - 1 por incluido llegar[i].
De lo contrario, comience una nueva subsecuencia:
- dp[arr[i]] = 1;
// C++ program to find the longest subsequence such that // the difference between adjacent elements is one using // Tabulation. #include using namespace std ; int longestSubseq ( vector < int >& arr ) { int n = arr . size (); // Base case: if the array has only // one element if ( n == 1 ) { return 1 ; } // Map to store the length of the longest subsequence unordered_map < int int > dp ; int ans = 1 ; // Loop through the array to fill the map // with subsequence lengths for ( int i = 0 ; i < n ; ++ i ) { // Check if the current element is adjacent // to another subsequence if ( dp . count ( arr [ i ] + 1 ) > 0 || dp . count ( arr [ i ] - 1 ) > 0 ) { dp [ arr [ i ]] = 1 + max ( dp [ arr [ i ] + 1 ] dp [ arr [ i ] - 1 ]); } else { dp [ arr [ i ]] = 1 ; } // Update the result with the maximum // subsequence length ans = max ( ans dp [ arr [ i ]]); } return ans ; } int main () { vector < int > arr = { 10 9 4 5 4 8 6 }; cout < < longestSubseq ( arr ); return 0 ; }
Java // Java code to find the longest subsequence such that // the difference between adjacent elements // is one using Tabulation. import java.util.HashMap ; import java.util.ArrayList ; class GfG { static int longestSubseq ( ArrayList < Integer > arr ) { int n = arr . size (); // Base case: if the array has only one element if ( n == 1 ) { return 1 ; } // Map to store the length of the longest subsequence HashMap < Integer Integer > dp = new HashMap <> (); int ans = 1 ; // Loop through the array to fill the map // with subsequence lengths for ( int i = 0 ; i < n ; ++ i ) { // Check if the current element is adjacent // to another subsequence if ( dp . containsKey ( arr . get ( i ) + 1 ) || dp . containsKey ( arr . get ( i ) - 1 )) { dp . put ( arr . get ( i ) 1 + Math . max ( dp . getOrDefault ( arr . get ( i ) + 1 0 ) dp . getOrDefault ( arr . get ( i ) - 1 0 ))); } else { dp . put ( arr . get ( i ) 1 ); } // Update the result with the maximum // subsequence length ans = Math . max ( ans dp . get ( arr . get ( i ))); } return ans ; } public static void main ( String [] args ) { ArrayList < Integer > arr = new ArrayList <> (); arr . add ( 10 ); arr . add ( 9 ); arr . add ( 4 ); arr . add ( 5 ); arr . add ( 4 ); arr . add ( 8 ); arr . add ( 6 ); System . out . println ( longestSubseq ( arr )); } }
Python # Python code to find the longest subsequence such that # the difference between adjacent elements is # one using Tabulation. def longestSubseq ( arr ): n = len ( arr ) # Base case: if the array has only one element if n == 1 : return 1 # Dictionary to store the length of the # longest subsequence dp = {} ans = 1 for i in range ( n ): # Check if the current element is adjacent to # another subsequence if arr [ i ] + 1 in dp or arr [ i ] - 1 in dp : dp [ arr [ i ]] = 1 + max ( dp . get ( arr [ i ] + 1 0 ) dp . get ( arr [ i ] - 1 0 )) else : dp [ arr [ i ]] = 1 # Update the result with the maximum # subsequence length ans = max ( ans dp [ arr [ i ]]) return ans if __name__ == '__main__' : arr = [ 10 9 4 5 4 8 6 ] print ( longestSubseq ( arr ))
C# // C# code to find the longest subsequence such that // the difference between adjacent elements // is one using Tabulation. using System ; using System.Collections.Generic ; class GfG { static int longestSubseq ( List < int > arr ) { int n = arr . Count ; // Base case: if the array has only one element if ( n == 1 ) { return 1 ; } // Map to store the length of the longest subsequence Dictionary < int int > dp = new Dictionary < int int > (); int ans = 1 ; // Loop through the array to fill the map with // subsequence lengths for ( int i = 0 ; i < n ; ++ i ) { // Check if the current element is adjacent to // another subsequence if ( dp . ContainsKey ( arr [ i ] + 1 ) || dp . ContainsKey ( arr [ i ] - 1 )) { dp [ arr [ i ]] = 1 + Math . Max ( dp . GetValueOrDefault ( arr [ i ] + 1 0 ) dp . GetValueOrDefault ( arr [ i ] - 1 0 )); } else { dp [ arr [ i ]] = 1 ; } // Update the result with the maximum // subsequence length ans = Math . Max ( ans dp [ arr [ i ]]); } return ans ; } static void Main ( string [] args ) { List < int > arr = new List < int > { 10 9 4 5 4 8 6 }; Console . WriteLine ( longestSubseq ( arr )); } }
JavaScript // Function to find the longest subsequence such that // the difference between adjacent elements // is one using Tabulation. function longestSubseq ( arr ) { const n = arr . length ; // Base case: if the array has only one element if ( n === 1 ) { return 1 ; } // Object to store the length of the // longest subsequence let dp = {}; let ans = 1 ; // Loop through the array to fill the object // with subsequence lengths for ( let i = 0 ; i < n ; i ++ ) { // Check if the current element is adjacent to // another subsequence if (( arr [ i ] + 1 ) in dp || ( arr [ i ] - 1 ) in dp ) { dp [ arr [ i ]] = 1 + Math . max ( dp [ arr [ i ] + 1 ] || 0 dp [ arr [ i ] - 1 ] || 0 ); } else { dp [ arr [ i ]] = 1 ; } // Update the result with the maximum // subsequence length ans = Math . max ( ans dp [ arr [ i ]]); } return ans ; } const arr = [ 10 9 4 5 4 8 6 ]; console . log ( longestSubseq ( arr ));
Producción
3Crear cuestionario
