Dada una array de enteros, encuentre la longitud de la subsecuencia más larga de modo que los elementos de la subsecuencia sean enteros consecutivos, los números consecutivos pueden estar en cualquier orden.
Ejemplos :
C++
// C++ program to find longest // contiguous subsequence #include <bits/stdc++.h> using namespace std; // Returns length of the longest // contiguous subsequence int findLongestConseqSubseq(int arr[], int n) { int ans = 0, count = 0; // sort the array sort(arr, arr + n); vector<int> v; v.push_back(arr[0]); //insert repeated elements only once in the vector for (int i = 1; i < n; i++) { if (arr[i] != arr[i - 1]) v.push_back(arr[i]); } // find the maximum length // by traversing the array for (int i = 0; i < v.size(); i++) { // Check if the current element is equal // to previous element +1 if (i > 0 && v[i] == v[i - 1] + 1) count++; // reset the count else count = 1; // update the maximum ans = max(ans, count); } return ans; } // Driver code int main() { int arr[] = { 1, 2, 2, 3 }; int n = sizeof arr / sizeof arr[0]; cout << "Length of the Longest contiguous subsequence " "is " << findLongestConseqSubseq(arr, n); return 0; }
Java
// Java program to find longest // contiguous subsequence import java.io.*; import java.util.*; class GFG { static int findLongestConseqSubseq(int arr[], int n) { // Sort the array Arrays.sort(arr); int ans = 0, count = 0; ArrayList<Integer> v = new ArrayList<Integer>(); v.add(10); // Insert repeated elements // only once in the vector for (int i = 1; i < n; i++) { if (arr[i] != arr[i - 1]) v.add(arr[i]); } // Find the maximum length // by traversing the array for (int i = 0; i < v.size(); i++) { // Check if the current element is // equal to previous element +1 if (i > 0 &&v.get(i) == v.get(i - 1) + 1) count++; else count = 1; // Update the maximum ans = Math.max(ans, count); } return ans; } // Driver code public static void main(String[] args) { int arr[] = { 1, 9, 3, 10, 4, 20, 2 }; int n = arr.length; System.out.println( "Length of the Longest " + "contiguous subsequence is " + findLongestConseqSubseq(arr, n)); } } // This code is contributed by parascoding
Python3
# Python3 program to find longest # contiguous subsequence # Returns length of the longest # contiguous subsequence def findLongestConseqSubseq(arr, n): ans = 0 count = 0 # Sort the array arr.sort() v = [] v.append(arr[0]) # Insert repeated elements only # once in the vector for i in range(1, n): if (arr[i] != arr[i - 1]): v.append(arr[i]) # Find the maximum length # by traversing the array for i in range(len(v)): # Check if the current element is # equal to previous element +1 if (i > 0 and v[i] == v[i - 1] + 1): count += 1 # Reset the count else: count = 1 # Update the maximum ans = max(ans, count) return ans # Driver code arr = [ 1, 2, 2, 3 ] n = len(arr) print("Length of the Longest contiguous subsequence is", findLongestConseqSubseq(arr, n)) # This code is contributed by avanitrachhadiya2155
C#
// C# program to find longest // contiguous subsequence using System; using System.Collections.Generic; class GFG{ static int findLongestConseqSubseq(int[] arr, int n) { // Sort the array Array.Sort(arr); int ans = 0, count = 0; List<int> v = new List<int>(); v.Add(10); // Insert repeated elements // only once in the vector for(int i = 1; i < n; i++) { if (arr[i] != arr[i - 1]) v.Add(arr[i]); } // Find the maximum length // by traversing the array for(int i = 0; i < v.Count; i++) { // Check if the current element is // equal to previous element +1 if (i > 0 && v[i] == v[i - 1] + 1) count++; else count = 1; // Update the maximum ans = Math.Max(ans, count); } return ans; } // Driver code static void Main() { int[] arr = { 1, 9, 3, 10, 4, 20, 2 }; int n = arr.Length; Console.WriteLine("Length of the Longest " + "contiguous subsequence is " + findLongestConseqSubseq(arr, n)); } } // This code is contributed by divyeshrabadiya07
Javascript
<script> // JavaScript program to find longest // contiguous subsequence // Returns length of the longest // contiguous subsequence function findLongestConseqSubseq(arr, n) { let ans = 0, count = 0; // sort the array arr.sort(function (a, b) { return a - b; }) var v = []; v.push(arr[0]); //insert repeated elements only once in the vector for (let i = 1; i < n; i++) { if (arr[i] != arr[i - 1]) v.push(arr[i]); } // find the maximum length // by traversing the array for (let i = 0; i < v.length; i++) { // Check if the current element is equal // to previous element +1 if (i > 0 && v[i] == v[i - 1] + 1) count++; // reset the count else count = 1; // update the maximum ans = Math.max(ans, count); } return ans; } // Driver code let arr = [1, 2, 2, 3]; let n = arr.length; document.write( "Length of the Longest contiguous subsequence is " +findLongestConseqSubseq(arr, n) ); // This code is contributed by Potta Lokesh </script>
C++
// C++ program to find longest // contiguous subsequence #include <bits/stdc++.h> using namespace std; // Returns length of the longest // contiguous subsequence int findLongestConseqSubseq(int arr[], int n) { unordered_set<int> S; int ans = 0; // Hash all the array elements for (int i = 0; i < n; i++) S.insert(arr[i]); // check each possible sequence from // the start then update optimal length for (int i = 0; i < n; i++) { // if current element is the starting // element of a sequence if (S.find(arr[i] - 1) == S.end()) { // Then check for next elements // in the sequence int j = arr[i]; while (S.find(j) != S.end()) j++; // update optimal length if // this length is more ans = max(ans, j - arr[i]); } } return ans; } // Driver code int main() { int arr[] = { 1, 9, 3, 10, 4, 20, 2 }; int n = sizeof arr / sizeof arr[0]; cout << "Length of the Longest contiguous subsequence " "is " << findLongestConseqSubseq(arr, n); return 0; }
Java
// Java program to find longest // consecutive subsequence import java.io.*; import java.util.*; class ArrayElements { // Returns length of the longest // consecutive subsequence static int findLongestConseqSubseq(int arr[], int n) { HashSet<Integer> S = new HashSet<Integer>(); int ans = 0; // Hash all the array elements for (int i = 0; i < n; ++i) S.add(arr[i]); // check each possible sequence from the start // then update optimal length for (int i = 0; i < n; ++i) { // if current element is the starting // element of a sequence if (!S.contains(arr[i] - 1)) { // Then check for next elements // in the sequence int j = arr[i]; while (S.contains(j)) j++; // update optimal length if this // length is more if (ans < j - arr[i]) ans = j - arr[i]; } } return ans; } // Driver Code public static void main(String args[]) { int arr[] = { 1, 9, 3, 10, 4, 20, 2 }; int n = arr.length; System.out.println( "Length of the Longest consecutive subsequence is " + findLongestConseqSubseq(arr, n)); } } // This code is contributed by Aakash Hasija
Python3
# Python program to find longest contiguous subsequence def findLongestConseqSubseq(arr, n): s = set() ans = 0 # Hash all the array elements for ele in arr: s.add(ele) # check each possible sequence from the start # then update optimal length for i in range(n): # if current element is the starting # element of a sequence if (arr[i]-1) not in s: # Then check for next elements in the # sequence j = arr[i] while(j in s): j += 1 # update optimal length if this length # is more ans = max(ans, j-arr[i]) return ans # Driver code if __name__ == '__main__': n = 7 arr = [1, 9, 3, 10, 4, 20, 2] print ("Length of the Longest contiguous subsequence is ",findLongestConseqSubseq(arr, n)) # Contributed by: Harshit Sidhwa
C#
using System; using System.Collections.Generic; // C# program to find longest consecutive subsequence public class ArrayElements { // Returns length of the // longest consecutive subsequence public static int findLongestConseqSubseq(int[] arr, int n) { HashSet<int> S = new HashSet<int>(); int ans = 0; // Hash all the array elements for (int i = 0; i < n; ++i) { S.Add(arr[i]); } // check each possible sequence from the start // then update optimal length for (int i = 0; i < n; ++i) { // if current element is the starting // element of a sequence if (!S.Contains(arr[i] - 1)) { // Then check for next elements in the // sequence int j = arr[i]; while (S.Contains(j)) { j++; } // update optimal length if this length // is more if (ans < j - arr[i]) { ans = j - arr[i]; } } } return ans; } // Driver code public static void Main(string[] args) { int[] arr = new int[] { 1, 9, 3, 10, 4, 20, 2 }; int n = arr.Length; Console.WriteLine( "Length of the Longest consecutive subsequence is " + findLongestConseqSubseq(arr, n)); } } // This code is contributed by Shrikant13
Javascript
<script> // Javascript program to find longest // contiguous subsequence // Returns length of the longest // contiguous subsequence function findLongestConseqSubseq(arr, n) { let S = new Set(); let ans = 0; // Hash all the array elements for (let i = 0; i < n; i++) S.add(arr[i]); // check each possible sequence from // the start then update optimal length for (let i = 0; i < n; i++) { // if current element is the starting // element of a sequence if (!S.has(arr[i] - 1)) { // Then check for next elements // in the sequence let j = arr[i]; while (S.has(j)) j++; // update optimal length if // this length is more ans = Math.max(ans, j - arr[i]); } } return ans; } // Driver code let arr = [1, 9, 3, 10, 4, 20, 2]; let n = arr.length; document.write("Length of the Longest contiguous subsequence is " + findLongestConseqSubseq(arr, n)); // This code is contributed by gfgking. </script>
C++
// CPP program for the above approach #include <bits/stdc++.h> using namespace std; int findLongestConseqSubseq(int arr[], int N) { priority_queue<int, vector<int>, greater<int> > pq; for (int i = 0; i < N; i++) { // adding element from // array to PriorityQueue pq.push(arr[i]); } // Storing the first element // of the Priority Queue // This first element is also // the smallest element int prev = pq.top(); pq.pop(); // Taking a counter variable with value 1 int c = 1; // Storing value of max as 1 // as there will always be // one element int max = 1; while (!pq.empty()) { // check if current peek // element minus previous // element is greater than // 1 This is done because // if it's greater than 1 // then the sequence // doesn't start or is broken here if (pq.top() - prev > 1) { // Store the value of counter to 1 // As new sequence may begin c = 1; // Update the previous position with the // current peek And remove it prev = pq.top(); pq.pop(); } // Check if the previous // element and peek are same else if (pq.top() - prev == 0) { // Update the previous position with the // current peek And remove it prev = pq.top(); pq.pop(); } // If the difference // between previous element and peek is 1 else { // Update the counter // These are consecutive elements c++; // Update the previous position // with the current peek And remove it prev = pq.top(); pq.pop(); } // Check if current longest // subsequence is the greatest if (max < c) { // Store the current subsequence count as // max max = c; } } return max; } // Driver Code int main() { int arr[] = { 1, 9, 3, 10, 4, 20, 2 }; int n = 7; cout << "Length of the Longest consecutive subsequence " "is " << findLongestConseqSubseq(arr, n); return 0; } // this code is contributed by Manu Pathria
Java
// Java Program to find longest consecutive // subsequence This Program uses Priority Queue import java.io.*; import java.util.PriorityQueue; public class Longset_Sub { // return the length of the longest // subsequence of consecutive integers static int findLongestConseqSubseq(int arr[], int N) { PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); for (int i = 0; i < N; i++) { // adding element from // array to PriorityQueue pq.add(arr[i]); } // Storing the first element // of the Priority Queue // This first element is also // the smallest element int prev = pq.poll(); // Taking a counter variable with value 1 int c = 1; // Storing value of max as 1 // as there will always be // one element int max = 1; for (int i = 1; i < N; i++) { // check if current peek // element minus previous // element is greater than // 1 This is done because // if it's greater than 1 // then the sequence // doesn't start or is broken here if (pq.peek() - prev > 1) { // Store the value of counter to 1 // As new sequence may begin c = 1; // Update the previous position with the // current peek And remove it prev = pq.poll(); } // Check if the previous // element and peek are same else if (pq.peek() - prev == 0) { // Update the previous position with the // current peek And remove it prev = pq.poll(); } // if the difference // between previous element and peek is 1 else { // Update the counter // These are consecutive elements c++; // Update the previous position // with the current peek And remove it prev = pq.poll(); } // Check if current longest // subsequence is the greatest if (max < c) { // Store the current subsequence count as // max max = c; } } return max; } // Driver Code public static void main(String args[]) throws IOException { int arr[] = { 1, 9, 3, 10, 4, 20, 2 }; int n = arr.length; System.out.println( "Length of the Longest consecutive subsequence is " + findLongestConseqSubseq(arr, n)); } } // This code is contributed by Sudipa Sarkar
Python3
# Python program for the above approach import bisect def findLongestConseqSubseq(arr,N): pq = [] for i in range(N): # adding element from # array to PriorityQueue bisect.insort(pq,arr[i]) # Storing the first element # of the Priority Queue # This first element is also # the smallest element prev = pq[0] pq.pop(0) # Taking a counter variable with value 1 c=1 # Storing value of max as 1 # as there will always be # one element max = 1 while(len(pq)): # check if current peek # element minus previous # element is greater than # 1 This is done because # if it's greater than 1 # then the sequence # doesn't start or is broken here if(pq[0] - prev > 1): # Store the value of counter to 1 # As new sequence may begin c = 1 # Update the previous position with the # current peek And remove it prev = pq[0] pq.pop(0) # Check if the previous # element and peek are same elif(pq[0] - prev == 0): # Update the previous position with the # current peek And remove it prev = pq[0] pq.pop(0) # If the difference # between previous element and peek is 1 else: # Update the counter # These are consecutive elements c = c +1 # Update the previous position # with the current peek And remove it prev = pq[0] pq.pop(0) # Check if current longest # subsequence is the greatest if(max < c): # Store the current subsequence count as # max max = c return max # Driver Code arr = [1, 9, 3, 10, 4, 20, 2] n = 7 print("Length of the Longest consecutive subsequence is {}".format(findLongestConseqSubseq(arr, n))) # This code is contributed by Pushpesh Raj
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG { // return the length of the longest // subsequence of consecutive integers static int findLongestConseqSubseq(int[] arr, int N) { List<int> pq = new List<int>(); for (int i = 0; i < N; i++) { // adding element from // array to PriorityQueue pq.Add(arr[i]); pq.Sort(); } // Storing the first element // of the Priority Queue // This first element is also // the smallest element int prev = pq[0]; // Taking a counter variable with value 1 int c = 1; // Storing value of max as 1 // as there will always be // one element int max = 1; for (int i = 1; i < N; i++) { // check if current peek // element minus previous // element is greater than // 1 This is done because // if it's greater than 1 // then the sequence // doesn't start or is broken here if (pq[0] - prev > 1) { // Store the value of counter to 1 // As new sequence may begin c = 1; // Update the previous position with the // current peek And remove it prev = pq[0]; pq.RemoveAt(0); } // Check if the previous // element and peek are same else if (pq[0] - prev == 0) { // Update the previous position with the // current peek And remove it prev = pq[0]; pq.RemoveAt(0); } // if the difference // between previous element and peek is 1 else { // Update the counter // These are consecutive elements c++; // Update the previous position // with the current peek And remove it prev = pq[0]; pq.RemoveAt(0); } // Check if current longest // subsequence is the greatest if (max < c) { // Store the current subsequence count as // max max = c; } } return max; } // Driver Code public static void Main() { int[] arr = { 1, 9, 3, 10, 4, 20, 2 }; int n = arr.Length; Console.WriteLine( "Length of the Longest consecutive subsequence is " + findLongestConseqSubseq(arr, n)); } } // This code is contributed by code_hunt.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA