인접한 부분의 차이가 1이 되는 가장 긴 부분 수열
GfG Practice에서 사용해 보세요. 
산출
산출
산출
주어진 a 배열 배열[] ~의 사이즈 n 임무는 그것을 찾는 것이다. 가장 긴 부분 수열 그렇게 절대적인 차이 ~ 사이 인접 요소 1입니다.
예:
입력: arr[] = [10 9 4 5 4 8 6]
산출: 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++에 대한 재귀적 접근 방식 우리는 고려할 것이다 두 가지 경우 각 단계에서:
- 요소가 조건을 만족하는 경우( 절대적인 차이 인접한 요소 사이는 1) 우리 포함하다 그것을 순차적으로 처리하고 다음 단계로 넘어갑니다. 다음 요소.
- 그렇지 않으면 우리는 건너뛰다 그만큼 현재의 요소를 선택하고 다음 요소로 넘어갑니다.
수학적으로 재발 관계 다음과 같이 보일 것입니다:
- maximumSubseq(arr idx prev) = max(longestSubseq(arr idx + 1 prev) 1 + maximumSubseq(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(메모이제이션) 사용 ) - 오(n^2) 시간과 오(n^2) 공간
주의 깊게 살펴보면 위의 재귀 솔루션이 다음 두 가지 속성을 보유하고 있음을 알 수 있습니다. 동적 프로그래밍 :
1. 최적의 하부 구조: 다음과 같은 가장 긴 부분 수열을 찾는 솔루션입니다. 차이점 인접한 요소 사이의 문제는 더 작은 하위 문제의 최적 솔루션에서 파생될 수 있습니다. 특정 주어진 것에 대해 구체적으로 idx (현재 인덱스) 및 이전 (하위 시퀀스의 이전 인덱스) 재귀 관계를 다음과 같이 표현할 수 있습니다.
- subseqHelper(idx prev) = max(subseqHelper(idx + 1 prev) 1 + subseqHelper(idx + 1 idx))
2. 중복되는 하위 문제: 구현할 때 재귀적 문제를 해결하기 위한 접근 방식에서는 많은 하위 문제가 여러 번 계산되는 것을 볼 수 있습니다. 예를 들어 컴퓨팅할 때 subseqHelper(0 -1) 배열의 경우 도착 = [10 9 4 5] 하위 문제 subseqHelper(2 -1) 계산될 수 있다 다수의 타임스. 이러한 반복을 피하기 위해 우리는 메모이제이션을 사용하여 이전에 계산된 하위 문제의 결과를 저장합니다.
재귀적 솔루션에는 다음이 포함됩니다. 둘 매개변수:
- idx (배열의 현재 인덱스)
- 이전 (하위 시퀀스에 포함된 마지막 요소의 인덱스)
우리는 추적해야 해 두 매개변수 모두 그래서 우리는 2차원 배열 메모 ~의 크기 (n) x (n+1) . 우리는 -1이 포함된 2D 배열 메모 아직 하위 문제가 계산되지 않았음을 나타냅니다. 결과를 계산하기 전에 값이 다음과 같은지 확인합니다. 메모[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로 끝나는 가장 긴 부분 수열입니다.
모든 요소에 대해 도착[i] 배열에서: 만약 도착[i] + 1 또는 도착[i] - 1 dp에 존재합니다:
- dp[arr[i]] = 1 + max(dp[arr[i] + 1] dp[arr[i] - 1]);
이는 다음으로 끝나는 하위 시퀀스를 확장할 수 있음을 의미합니다. 도착[i] + 1 또는 도착[i] - 1 ~에 의해 포함 도착[i].
그렇지 않으면 새 하위 시퀀스를 시작합니다:
- 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퀴즈 만들기
