logo

TechCodeview

隣接するもの間の差が 1 であるような最長のサブシーケンス

GfG Practice で試してみる ' title=

を与えると 配列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) 空間

のために 再帰的アプローチ 検討させていただきます 2つのケース 各ステップで:

  • 要素が条件 ( 絶対差 隣接する要素間の距離は 1) 含む それを後続部分で実行し、次の部分に進みます。 次 要素。
  • そうでなければ私たちは スキップ の 現在 要素を選択して次の要素に進みます。

数学的には 再発関係 は次のようになります。

ユーザー名とは何ですか
  • longestSubseq(arr idx prev) = max(longestSubseq(arr idx + 1 prev) 1 +longestSubseq(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 の使用（メモ化） ) -  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) を保存します。 長さ 最も長いサブシーケンスの一部。これは、効率的に計算して更新するのに役立ちます。 後続 配列要素のすべての可能な値の長さ。

動的プログラミングの関係:

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++ 
// 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
クイズの作成