logo

TechCodeview

Najdaljše podzaporedje, tako da je razlika med sosednjima ena

Preizkusite na GfG Practice ' title=

Glede na a rray arr[] od velikost n naloga je najti najdaljše podzaporedje tako, da je absolutna razlika med sosednji elementi je 1.

Primeri: 

Vnos: arr[] = [10 9 4 5 4 8 6]
Izhod: 3
Pojasnilo: Tri možna podzaporedja dolžine 3 so [10 9 8] [4 5 4] in [4 5 6], kjer imajo sosednji elementi absolutno razliko 1. Nobenega veljavnega podzaporedja večje dolžine ni bilo mogoče oblikovati.

Vnos: arr[] = [1 2 3 4 5]
Izhod: 5
Pojasnilo: Vsi elementi so lahko vključeni v veljavno podzaporedje.



Uporaba rekurzije - O(2^n) časa in O(n) prostora

Za rekurzivni pristop bomo razmislili dva primera na vsakem koraku:

  • Če element izpolnjuje pogoj (the absolutna razlika med sosednjima elementoma je 1) mi vključujejo ga v naslednjem zaporedju in pojdite na naslednji element.
  • drugače mi preskoči the trenutno element in pojdite na naslednjega.

Matematično gledano ponovitveno razmerje bo videti takole:

jvm v Javi
  • longestSubseq(arr idx prev) = max(longestSubseq(arr idx + 1 prev) 1 + longestSubseq(arr idx + 1 idx))

Osnovni primer:

  • kdaj idx == arr.size() imamo dosežen konec niza torej vrni 0 (ker ni mogoče vključiti več elementov).
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));

Izhod 
3

Uporaba DP od zgoraj navzdol (memoizacija ) -  O(n^2)  Čas in  O(n^2)  Vesolje

Če natančno opazimo, lahko opazimo, da ima zgornja rekurzivna rešitev naslednji dve lastnosti  Dinamično programiranje :

1. Optimalna podkonstrukcija: Rešitev za iskanje najdaljšega podzaporedja, tako da je razlika med sosednjimi elementi je mogoče izpeljati iz optimalnih rešitev manjših podproblemov. Konkretno za vsako dano idx (trenutni indeks) in prev (prejšnji indeks v podzaporedju) lahko rekurzivno relacijo izrazimo takole:

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

2. Prekrivajoči se podproblemi: Pri izvajanju a rekurzivno pristop k rešitvi problema opazimo, da se številni podproblemi izračunajo večkrat. Na primer pri računanju subseqHelper(0 -1) za niz arr = [10 9 4 5] podproblem subseqHelper(2 -1) se lahko izračuna večkratno krat. Da bi se izognili temu ponavljanju, uporabljamo memoizacijo za shranjevanje rezultatov predhodno izračunanih podproblemov.

Rekurzivna rešitev vključuje dva parametri:

  • idx (trenutni indeks v matriki).
  • prev (indeks zadnjega vključenega elementa v podzaporedju).

Moramo slediti oba parametra tako ustvarimo a Beležka 2D polja od velikost (n) x (n+1) . Inicializiramo 2D matrični memo z -1 da označite, da še ni bila izračunana nobena podproblema. Pred izračunom rezultata preverimo, ali je vrednost pri memo[idx][prev+1] je -1. Če je, izračunamo in trgovina rezultat. V nasprotnem primeru vrnemo shranjen rezultat.

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

Izhod 
3

Uporaba DP od spodaj navzgor (Tabelacija) -   O(n)  Čas in  O(n)  Vesolje

Pristop je podoben kot pri rekurzivno vendar namesto rekurzivne razčlenitve problema rešitev iterativno zgradimo v a način od spodaj navzgor.
Namesto rekurzije uporabljamo a hashmap dinamično programsko tabelo (dp) za shranjevanje dolžine najdaljših podzaporedij. To nam pomaga učinkovito izračunati in posodobiti podzaporedje dolžine za vse možne vrednosti elementov polja.

Relacija dinamičnega programiranja:

dp[x] predstavlja dolžina najdaljšega podzaporedja, ki se konča z elementom x.

Za vsak element pride[i] v nizu: Če arr[i] + 1 oz arr[i] - 1 obstaja v dp:

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

To pomeni, da lahko razširimo podzaporedja, ki se končajo z arr[i] + 1 oz arr[i] - 1 avtor vključno z arr[i].

V nasprotnem primeru začnite novo podzaporedje:

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

Izhod 
3
Ustvari kviz