Cea mai lungă succesiune astfel încât diferența dintre adiacenți este de unu
Încercați-l pe GfG Practice 
Ieșire
Ieșire
Ieșire
Având în vedere un a rray arr[] de marimea n sarcina este de a găsi cea mai lungă succesiune astfel încât diferenta absoluta între elemente adiacente este 1.
Exemple:
Intrare: arr[] = [10 9 4 5 4 8 6]
Ieșire: 3
Explicaţie: Cele trei subsecvențe posibile ale lungimii 3 sunt [10 9 8] [4 5 4] și [4 5 6] unde elementele adiacente au o diferență absolută de 1. Nu s-ar putea forma nicio subsecvență validă de lungime mai mare.
Intrare: arr[] = [1 2 3 4 5]
Ieșire: 5
Explicaţie: Toate elementele pot fi incluse în subsecvența valabilă.
Folosind recursiunea - O(2^n) Timp și O(n) Spațiu
C++Pentru abordare recursivă vom lua în considerare doua cazuri la fiecare pas:
- Dacă elementul îndeplinește condiția ( diferenta absoluta între elementele adiacente este 1) noi include aceasta în următorul și treceți la Următorul element.
- altfel noi sari peste cel actual element și treceți la următorul.
Matematic cel relație de recurență va arăta astfel:
- longestSubseq(arr idx prev) = max(longestSubseq(arr idx + 1 prev) 1 + longestSubseq(arr idx + 1 idx))
Caz de bază:
- Când idx == arr.size() avem atins sfârşitul matricei deci întoarce 0 (deoarece nu mai pot fi incluse elemente).
// 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 ));
Ieșire
3
Utilizarea de sus în jos DP (Memoization )- O(n^2) Timpul și O(n^2) Spaţiu
Dacă observăm cu atenție, putem observa că soluția recursivă de mai sus deține următoarele două proprietăți ale Programare dinamică :
1. Substructură optimă: Soluția pentru găsirea celei mai lungi secvențe astfel încât diferenţă între elementele adiacente este unul poate fi derivat din soluțiile optime ale subproblemelor mai mici. Specific pentru orice dat idx (indicele actual) și prev (indexul anterior în subsecvența) putem exprima relația recursivă astfel:
- subseqHelper(idx prev) = max(subseqHelper(idx + 1 prev) 1 + subseqHelper(idx + 1 idx))
2. Subprobleme suprapuse: La implementarea unui recursiv abordare pentru a rezolva problema observăm că multe subprobleme sunt calculate de mai multe ori. De exemplu, când se calculează subseqHelper(0 -1) pentru o matrice arr = [10 9 4 5] subproblema subseqHelper(2 -1) pot fi calculate multiplu ori. Pentru a evita această repetare, folosim memorizarea pentru a stoca rezultatele subproblemelor calculate anterior.
Soluția recursivă implică două parametri:
- idx (indexul curent din matrice).
- prev (indicele ultimului element inclus în subsecvență).
Trebuie să urmărim ambii parametri deci creăm o Memo de matrice 2D de dimensiune (n) x (n+1) . Inițializam Memo de matrice 2D cu -1 pentru a indica faptul că nu au fost încă calculate subprobleme. Înainte de a calcula un rezultat, verificăm dacă valoarea la notă[idx][prev+1] este -1. Dacă este, calculăm și magazin Rezultatul. În caz contrar, returnăm rezultatul stocat.
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 ));
Ieșire
3
Utilizarea DP de jos în sus (tabulare) - Pe) Timpul și Pe) Spaţiu
Abordarea este similară cu cea recursiv dar în loc să defalcăm problema recursiv, construim iterativ soluția în a manieră de jos în sus.
În loc să folosim recursiunea, folosim a hashmap tabel de programare dinamic bazat (dp) a stoca lungimi dintre cele mai lungi subsecvente. Acest lucru ne ajută să calculăm și să actualizăm eficient ulterior lungimi pentru toate valorile posibile ale elementelor matricei.
C++Relație de programare dinamică:
dp[x] reprezintă lungime a celei mai lungi subsecvențe care se termină cu elementul x.
Pentru fiecare element arr[i] în matrice: Dacă arr[i] + 1 sau arr[i] - 1 există în dp:
- dp[arr[i]] = 1 + max(dp[arr[i] + 1] dp[arr[i] - 1]);
Aceasta înseamnă că putem extinde subsecvențele care se termină cu arr[i] + 1 sau arr[i] - 1 de inclusiv arr[i].
În caz contrar, începeți o nouă secvență:
- 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 ));
Ieșire
3Creați un test
