logo

TechCodeview

Längste Teilfolge, bei der der Unterschied zwischen benachbarten Folgen eins beträgt

Probieren Sie es bei GfG Practice aus ' title=

Angesichts eines a rray arr[] von Größe n Die Aufgabe besteht darin, das zu finden längste Teilsequenz so dass die absoluter Unterschied zwischen angrenzende Elemente ist 1.

Beispiele: 

Eingang: arr[] = [10 9 4 5 4 8 6]
Ausgabe: 3
Erläuterung: Die drei möglichen Teilfolgen der Länge 3 sind [10 9 8] [4 5 4] und [4 5 6], wobei benachbarte Elemente eine absolute Differenz von 1 haben. Es konnte keine gültige Teilfolge größerer Länge gebildet werden.

Eingang: arr[] = [1 2 3 4 5]
Ausgabe: 5
Erläuterung: Alle Elemente können in die gültige Teilsequenz aufgenommen werden.



Rekursion verwenden – O(2^n) Zeit und O(n) Raum

Für die rekursiver Ansatz wir werden darüber nachdenken zwei Fälle bei jedem Schritt:

  • Wenn das Element die Bedingung erfüllt (die absoluter Unterschied zwischen benachbarten Elementen ist 1) wir enthalten es in der Folge und fahren Sie mit dem fort nächste Element.
  • sonst wir überspringen Die aktuell Element und fahren Sie mit dem nächsten fort.

Mathematisch gesehen ist das Wiederholungsbeziehung wird wie folgt aussehen:

Linkliste in Java
  • longestSubseq(arr idx prev) = max(longestSubseq(arr idx + 1 prev) 1 + longestSubseq(arr idx + 1 idx))

Basisfall:

  • Wann idx == arr.size() wir haben erreicht das Ende des Arrays also 0 zurückgeben (da keine weiteren Elemente eingebunden werden können).
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));

Ausgabe 
3

Verwendung von Top-Down-DP (Memoization). ) -  O(n^2)  Zeit und  O(n^2)  Raum

Wenn wir genau hinsehen, können wir feststellen, dass die obige rekursive Lösung die folgenden zwei Eigenschaften von aufweist  Dynamische Programmierung :

1. Optimaler Unterbau: Die Lösung, um die längste Teilfolge zu finden, sodass die Unterschied zwischen benachbarten Elementen ist, kann man daraus die optimalen Lösungen kleinerer Teilprobleme ableiten. Speziell für jeden gegebenen idx (aktueller Index) und vorh (vorheriger Index in der Untersequenz) können wir die rekursive Beziehung wie folgt ausdrücken:

  • subseqHelper(idx prev) = max(subseqHelper(idx + 1 prev) 1 + subseqHelper(idx + 1 idx))

2. Überlappende Teilprobleme: Bei der Implementierung eines rekursiv Beim Ansatz zur Lösung des Problems beobachten wir, dass viele Teilprobleme mehrfach berechnet werden. Zum Beispiel beim Rechnen subseqHelper(0 -1) für ein Array arr = [10 9 4 5] das Teilproblem subseqHelper(2 -1) berechnet werden kann mehrere mal. Um diese Wiederholung zu vermeiden, verwenden wir die Memoisierung, um die Ergebnisse zuvor berechneter Teilprobleme zu speichern.

Die rekursive Lösung beinhaltet zwei Parameter:

  • idx (der aktuelle Index im Array).
  • vorh (der Index des letzten enthaltenen Elements in der Teilsequenz).

Wir müssen nachverfolgen beide Parameter Also erstellen wir eine 2D-Array-Memo von Größe (n) x (n+1) . Wir initialisieren die 2D-Array-Memo mit -1 um anzuzeigen, dass noch keine Teilprobleme berechnet wurden. Bevor wir ein Ergebnis berechnen, prüfen wir, ob der Wert bei liegt memo[idx][prev+1] ist -1. Wenn ja, berechnen wir und speichern das Ergebnis. Andernfalls geben wir das gespeicherte Ergebnis zurück.

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));

Ausgabe 
3

Verwenden von Bottom-Up-DP (Tabulation) –   An)  Zeit und  An)  Raum

Der Ansatz ähnelt dem rekursiv Methode, aber anstatt das Problem rekursiv aufzuschlüsseln, bauen wir die Lösung iterativ in a auf von unten nach oben.
Anstelle der Rekursion verwenden wir a Hashmap basierte dynamische Programmiertabelle (dp) zum Speichern der Längen der längsten Teilsequenzen. Dies hilft uns, die Daten effizient zu berechnen und zu aktualisieren Folge Längen für alle möglichen Werte von Array-Elementen.

Dynamische Programmierbeziehung:

dp[x] stellt die dar Länge der längsten Teilfolge, die mit dem Element x endet.

Für jedes Element arr[i] im Array: If arr[i] + 1 oder arr[i] - 1 existiert in dp:

  • dp[arr[i]] = 1 + max(dp[arr[i] + 1] dp[arr[i] - 1]);

Das bedeutet, dass wir die Teilfolgen erweitern können, die mit enden arr[i] + 1 oder arr[i] - 1 von einschließlich arr[i].

Andernfalls starten Sie eine neue Teilsequenz:

  • 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));

Ausgabe 
3
Quiz erstellen