Najdłuższy podciąg taki, że różnica między sąsiednimi wynosi jeden
Wypróbuj w praktyce GfG 
Wyjście
Wyjście
Wyjście
Biorąc pod uwagę a rray tablica [] z rozmiar nr zadaniem jest znaleźć najdłuższy podciąg takie, że absolutna różnica między sąsiadujące elementy jest 1.
Przykłady:
Wejście: tablica [] = [10 9 4 5 4 8 6]
Wyjście: 3
Wyjaśnienie: Trzy możliwe podciągi o długości 3 to [10 9 8] [4 5 4] i [4 5 6], gdzie sąsiadujące elementy mają różnicę bezwzględną 1. Nie można utworzyć żadnego prawidłowego podciągu o większej długości.
Wejście: tablica [] = [1 2 3 4 5]
Wyjście: 5
Wyjaśnienie: Wszystkie elementy mogą być zawarte w prawidłowym podciągu.
Korzystanie z rekurencji - O(2^n) czasu i O(n) przestrzeni
C++Dla podejście rekurencyjne rozważymy dwa przypadki na każdym kroku:
- Jeśli element spełnia warunek (tzw absolutna różnica pomiędzy sąsiednimi elementami wynosi 1) we włączać to w dalszej kolejności i przejdź do Następny element.
- inaczej my pominąć the aktualny element i przejdź do następnego.
Matematycznie relacja powtarzalności będzie wyglądać następująco:
- longestSubseq(arr idx prev) = max(najdłuższySubseq(arr idx + 1 prev) 1 + longestSubseq(arr idx + 1 idx))
Obudowa podstawowa:
- Gdy idx == tablica.rozmiar() mamy osiągnięty koniec tablicy tak zwróć 0 (ponieważ nie można dodać więcej elementów).
// 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 ));
Wyjście
3
Korzystanie z odgórnego DP (Memoization ) - O(n^2) Czas i O(n^2) Przestrzeń
Jeśli uważnie zauważymy, możemy zauważyć, że powyższe rozwiązanie rekurencyjne posiada następujące dwie właściwości Programowanie dynamiczne :
1. Optymalna podbudowa: Rozwiązanie problemu znalezienia najdłuższego podciągu takiego, że różnica między sąsiednimi elementami można wyprowadzić z optymalnych rozwiązań mniejszych podproblemów. Konkretnie dla każdego idx (aktualny indeks) i poprzednie (poprzedni indeks w podciągu) relację rekurencyjną możemy wyrazić następująco:
- subseqHelper(idx poprzedni) = max(subseqHelper(idx + 1 poprzedni) 1 + subseqHelper(idx + 1 idx))
2. Nakładające się podproblemy: Podczas wdrażania A rekurencyjne podejścia do rozwiązania problemu zauważamy, że wiele podproblemów jest obliczanych wielokrotnie. Na przykład podczas obliczeń subseqHelper(0 -1) dla tablicy tablica = [10 9 4 5] podproblem subseqHelper(2 -1) może zostać obliczona wiele czasy. Aby uniknąć takich powtórzeń, używamy zapamiętywania do przechowywania wyników wcześniej obliczonych podproblemów.
Rozwiązanie rekurencyjne obejmuje dwa parametry:
- idx (bieżący indeks w tablicy).
- poprzednie (indeks ostatniego zawartego elementu w podciągu).
Musimy śledzić oba parametry więc tworzymy Notatka tablicowa 2D z rozmiar (n) x (n+1) . Inicjujemy Notatka tablicowa 2D z -1 aby wskazać, że nie obliczono jeszcze żadnych podproblemów. Przed obliczeniem wyniku sprawdzamy, czy wartość przy notatka[idx][poprzednia+1] wynosi -1. Jeśli tak, obliczamy i sklep wynik. W przeciwnym razie zwracamy zapisany wynik.
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 ));
Wyjście
3
Korzystanie z DP od dołu do góry (tabulacja) – NA) Czas i NA) Przestrzeń
Podejście jest podobne do rekurencyjne metodę, ale zamiast rekurencyjnie rozkładać problem, iteracyjnie budujemy rozwiązanie w pliku a sposób oddolny.
Zamiast używać rekurencji, używamy a mapa skrótów oparta na tabeli programowania dynamicznego (dp) do przechowywania długości z najdłuższych podciągów. Pomaga nam to skutecznie obliczać i aktualizować podsekwencja długości wszystkich możliwych wartości elementów tablicy.
C++Relacja programowania dynamicznego:
dp[x] reprezentuje długość najdłuższego podciągu zakończonego elementem x.
Dla każdego elementu Arr[i] w tablicy: Jeśli arr[i] + 1 Lub arr[i] - 1 istnieje w dp:
- dp[arr[i]] = 1 + max(dp[arr[i] + 1] dp[arr[i] - 1]);
Oznacza to, że możemy przedłużyć podciągi kończące się na arr[i] + 1 Lub arr[i] - 1 przez w tym arr[i].
W przeciwnym razie rozpocznij nowy podciąg:
- 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 ));
Wyjście
3Utwórz quiz
