Given a sequence of positive integers of length N. The only operation allowed is to insert a single integer of any value at any position in the sequence. The task is to find the sub-sequence of maximum length that contains consecutive values in increasing order.
Examples:
Input: arr[] = {2, 1, 4, 5}
Output: 4
Insert element with value 3 at the 3rd position.(1 based indexing)
The new sequence becomes {2, 1, 3, 4, 5}
Longest consecutive sub-sequence would be {2, 3, 4, 5}Input: arr[] = {2, 1, 2, 3, 5, 7} c
Output: 5
Approach: The idea is to use Dynamic Programming.
Let dp[val][0] be the length of required subsequence that ends in an element equal to val and the element is not inserted yet. Let dp[val][1] be the length of required subsequence that ends in an element equal to val and some element has been inserted already.
Now break the problem into its subproblems as follows:
To calculate dp[val][0], as no element in inserted, the length of the subsequence will increase by 1 from its previous value
dp[val][0] = 1 + dp[val – 1][0].
To calculate dp[val][1], consider these two cases:
- When the element is already inserted for (val-1), then there would be an increment of length 1 from dp[ val-1 ][ 1 ]
- When the element has not been inserted yet, then the element with value (val-1) can be inserted . Hence there would be an increment of length 2 from dp[ val-2 ][ 0 ].
Take maximum of both the above cases.
dp[val][1] = max(1 + dp[val – 1][1], 2 + dp[val – 2][0]).
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to return the length of longest// Consecutive subsequence after inserting an elementint LongestConsSeq(int arr[], int N){ // Variable to find maximum value of the array int maxval = 1; // Calculating maximum value of the array for (int i = 0; i < N; i += 1) { maxval = max(maxval, arr[i]); } // Declaring the DP table int dp[maxval + 1][2] = { 0 }; // Variable to store the maximum length int ans = 1; // Iterating for every value present in the array for (int i = 0; i < N; i += 1) { // Recurrence for dp[val][0] dp[arr[i]][0] = (1 + dp[arr[i] - 1][0]); // No value can be inserted before 1, // hence the element value should be // greater than 1 for this recurrence relation if (arr[i] >= 2) // Recurrence for dp[val][1] dp[arr[i]][1] = max(1 + dp[arr[i] - 1][1], 2 + dp[arr[i] - 2][0]); else // Maximum length of consecutive sequence // ending at 1 is equal to 1 dp[arr[i]][1] = 1; // Update the ans variable with // the new maximum length possible ans = max(ans, dp[arr[i]][1]); } // Return the ans return ans;}// Driver codeint main(){ // Input array int arr[] = { 2, 1, 4, 5 }; int N = sizeof(arr) / sizeof(arr[0]); cout << LongestConsSeq(arr, N); return 0;} |
Java
// Java implementation of above approachclass GFG{ // Function to return the length of longest // consecutive subsequence after inserting an element static int LongestConsSeq(int [] arr, int N) { // Variable to find maximum value of the array int maxval = 1; // Calculating maximum value of the array for (int i = 0; i < N; i += 1) { maxval = Math. max(maxval, arr[i]); } // Declaring the DP table int [][] dp = new int[maxval + 1][2]; // Variable to store the maximum length int ans = 1; // Iterating for every value present in the array for (int i = 0; i < N; i += 1) { // Recurrence for dp[val][0] dp[arr[i]][0] = (1 + dp[arr[i] - 1][0]); // No value can be inserted before 1, // hence the element value should be // greater than 1 for this recurrence relation if (arr[i] >= 2) // Recurrence for dp[val][1] dp[arr[i]][1] = Math.max(1 + dp[arr[i] - 1][1], 2 + dp[arr[i] - 2][0]); else // Maximum length of consecutive sequence // ending at 1 is equal to 1 dp[arr[i]][1] = 1; // Update the ans variable with // the new maximum length possible ans = Math.max(ans, dp[arr[i]][1]); } // Return the ans return ans; } // Driver code public static void main (String[] args) { // Input array int [] arr = { 2, 1, 4, 5 }; int N = arr.length; System.out.println(LongestConsSeq(arr, N)); }}// This code is contributed by ihritik |
Python3
# Python3 implementation of above approach# Function to return the length of longest# consecutive subsequence after inserting an elementdef LongestConsSeq(arr, N): # Variable to find maximum value of the array maxval = 1 # Calculating maximum value of the array for i in range(N): maxval = max(maxval, arr[i]) # Declaring the DP table dp=[[ 0 for i in range(2)] for i in range(maxval + 1)] # Variable to store the maximum length ans = 1 # Iterating for every value present in the array for i in range(N): # Recurrence for dp[val][0] dp[arr[i]][0] = 1 + dp[arr[i] - 1][0] # No value can be inserted before 1, # hence the element value should be # greater than 1 for this recurrence relation if (arr[i] >= 2): # Recurrence for dp[val][1] dp[arr[i]][1] = max(1 + dp[arr[i] - 1][1], 2 + dp[arr[i] - 2][0]) else: # Maximum length of consecutive sequence # ending at 1 is equal to 1 dp[arr[i]][1] = 1 # Update the ans variable with # the new maximum length possible ans = max(ans, dp[arr[i]][1]) # Return the ans return ans# Driver codearr=[2, 1, 4, 5]N = len(arr)print(LongestConsSeq(arr, N))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of above approachusing System;class GFG{ // Function to return the length of longest // consecutive subsequence after inserting an element static int LongestConsSeq(int [] arr, int N) { // Variable to find maximum value of the array int maxval = 1; // Calculating maximum value of the array for (int i = 0; i < N; i += 1) { maxval =Math.Max(maxval, arr[i]); } // Declaring the DP table int [ , ] dp = new int[maxval + 1, 2]; // Variable to store the maximum length int ans = 1; // Iterating for every value present in the array for (int i = 0; i < N; i += 1) { // Recurrence for dp[val][0] dp[arr[i], 0] = (1 + dp[arr[i] - 1, 0]); // No value can be inserted before 1, // hence the element value should be // greater than 1 for this recurrence relation if (arr[i] >= 2) // Recurrence for dp[val][1] dp[arr[i], 1] = Math.Max(1 + dp[arr[i] - 1, 1], 2 + dp[arr[i] - 2, 0]); else // Maximum length of consecutive sequence // ending at 1 is equal to 1 dp[arr[i], 1] = 1; // Update the ans variable with // the new maximum length possible ans = Math.Max(ans, dp[arr[i], 1]); } // Return the ans return ans; } // Driver code public static void Main () { // Input array int [] arr = new int [] { 2, 1, 4, 5 }; int N = arr.Length; Console.WriteLine(LongestConsSeq(arr, N)); }}// This code is contributed by ihritik |
Javascript
<script>// Javascript implementation of above approach// Function to return the length of // longest consecutive subsequence// after inserting an elementfunction LongestConsSeq(arr, N){ // Variable to find maximum value of the array let maxval = 1; // Calculating maximum value of the array for(let i = 0; i < N; i += 1) { maxval = Math. max(maxval, arr[i]); } // Declaring the DP table let dp = new Array(maxval + 1); for(let i = 0; i < dp.length; i++) { dp[i] = new Array(2); for(let j = 0; j < 2; j++) dp[i][j] = 0; } // Variable to store the maximum length let ans = 1; // Iterating for every value present in the array for(let i = 0; i < N; i += 1) { // Recurrence for dp[val][0] dp[arr[i]][0] = (1 + dp[arr[i] - 1][0]); // No value can be inserted before 1, // hence the element value should be // greater than 1 for this recurrence relation if (arr[i] >= 2) // Recurrence for dp[val][1] dp[arr[i]][1] = Math.max(1 + dp[arr[i] - 1][1], 2 + dp[arr[i] - 2][0]); else // Maximum length of consecutive sequence // ending at 1 is equal to 1 dp[arr[i]][1] = 1; // Update the ans variable with // the new maximum length possible ans = Math.max(ans, dp[arr[i]][1]); } // Return the ans return ans;}// Driver codelet arr = [ 2, 1, 4, 5 ];let N = arr.length;document.write(LongestConsSeq(arr, N));// This code is contributed by unknown2108</script> |
Output:
4
Time Complexity: O(N)
Space Complexity: O(MaxValue) where MaxValue is the maximum value present in the array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
