隣接するもの間の差が 1 であるような最長のサブシーケンス
GfG Practice で試してみる 
出力
出力
出力
を与えると 配列arr[] の サイズn 課題はそれを見つけることです 最長のサブシーケンス そのような 絶対差 間 隣接する要素 は1です。
例:
入力： arr[] = [10 9 4 5 4 8 6]
出力： 3
説明： 長さ 3 の 3 つの可能なサブシーケンスは、[10 9 8] [4 5 4] および [4 5 6] です。ここで、隣接する要素の差の絶対値は 1 です。これより長い長さの有効なサブシーケンスは形成できません。
入力： arr[] = [1 2 3 4 5]
出力： 5
説明： すべての要素を有効なサブシーケンスに含めることができます。
再帰の使用 - O(2^n) 時間と O(n) 空間
C++のために 再帰的アプローチ 検討させていただきます 2つのケース 各ステップで:
- 要素が条件 ( 絶対差 隣接する要素間の距離は 1) 含む それを後続部分で実行し、次の部分に進みます。 次 要素。
- そうでなければ私たちは スキップ の 現在 要素を選択して次の要素に進みます。
数学的には 再発関係 は次のようになります。
- longestSubseq(arr idx prev) = max(longestSubseq(arr idx + 1 prev) 1 +longestSubseq(arr idx + 1 idx))
基本ケース:
- いつ idx == arr.size() 我々は持っています 到達した 配列の終わりなので 0を返す (これ以上要素を含めることはできないため)。
// 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 ));
出力
3
トップダウン DP の使用（メモ化） ) - O(n^2) 時間と O(n^2) 空間
注意して観察すると、上記の再帰的解決策には次の 2 つの特性があることがわかります。 動的プログラミング :
1. 最適な下部構造: 次のような最長のサブシーケンスを見つけるための解決策は、 違い 隣接する要素間の要素は、より小さな部分問題の最適解から導き出すことができます。具体的には、どのような場合でも いど (現在のインデックス) と 前へ (サブシーケンス内の前のインデックス) 再帰関係は次のように表現できます。
- subseqHelper(idx 前) = max(subseqHelper(idx + 1 前) 1 + subseqHelper(idx + 1 idx))
2. 重複する副問題: を実装するときは、 再帰的 問題を解決するアプローチでは、多くの部分問題が複数回計算されることがわかります。たとえば計算するとき subseqHelper(0 -1) 配列の場合 arr = [10 9 4 5] 副次的な問題 subseqHelper(2 -1) 計算されるかもしれない 複数 回。この繰り返しを避けるために、メモ化を使用して、以前に計算された部分問題の結果を保存します。
再帰的な解決策には以下が含まれます 二 パラメータ:
- いど (配列内の現在のインデックス)。
- 前へ (サブシーケンスに含まれる最後に含まれる要素のインデックス)。
追跡する必要があります 両方のパラメータ そこで、 2次元配列メモ の サイズ (n) x (n+1) 。を初期化します。 -1を付けた2次元配列メモ 部分問題がまだ計算されていないことを示します。結果を計算する前に、次の値が正しいかどうかを確認します。 メモ[idx][前+1] は -1 です。そうであれば、計算して、 店 結果。それ以外の場合は、保存された結果を返します。
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 ));
出力
3
ボトムアップ DP (集計) の使用 - の上） 時間と の上） 空間
アプローチは次のようなものです 再帰的 メソッドを使用しますが、問題を再帰的に分解するのではなく、反復的に解決策を構築します。 ボトムアップ方式。
再帰を使用する代わりに、 ハッシュマップ ベースの動的計画法テーブル (dp) を保存します。 長さ 最も長いサブシーケンスの一部。これは、効率的に計算して更新するのに役立ちます。 後続 配列要素のすべての可能な値の長さ。
C++動的プログラミングの関係:
dp[x] を表します 長さ 要素 x で終わる最長のサブシーケンス。
あらゆる要素について 到着しました 配列内: arr[i] + 1 または ar[i] - 1 dp に存在します:
- dp[arr[i]] = 1 + max(dp[arr[i] + 1] dp[arr[i] - 1]);
これは、で終わるサブシーケンスを拡張できることを意味します。 arr[i] + 1 または ar[i] - 1 による 含む あります。
それ以外の場合は、新しいサブシーケンスを開始します。
- 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 ));
出力
3クイズの作成
