logo

TechCodeview

인접한 부분의 차이가 1이 되는 가장 긴 부분 수열

GfG Practice에서 사용해 보세요. ' title=

주어진 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) 공간

에 대한 재귀적 접근 방식 우리는 고려할 것이다 두 가지 경우 각 단계에서:

  • 요소가 조건을 만족하는 경우( 절대적인 차이 인접한 요소 사이는 1) 우리 포함하다 그것을 순차적으로 처리하고 다음 단계로 넘어갑니다. 다음 요소.
  • 그렇지 않으면 우리는 건너뛰다 그만큼 현재의 요소를 선택하고 다음 요소로 넘어갑니다.

수학적으로 재발 관계 다음과 같이 보일 것입니다:

지도를 찢다
  • maximumSubseq(arr idx prev) = max(longestSubseq(arr idx + 1 prev) 1 + maximumSubseq(arr idx + 1 idx))

기본 사례:

  • 언제 idx == arr.size() 우리는 도달했다 그래서 배열의 끝 0을 반환 (더 이상 요소를 포함할 수 없기 때문에)
C++ 
// 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)를 저장합니다. 길이 가장 긴 부분 수열 중 이를 통해 효율적으로 계산하고 업데이트할 수 있습니다. 후속 배열 요소의 가능한 모든 값에 대한 길이입니다.

동적 프로그래밍 관계:

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++ 
// 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
퀴즈 만들기