Given an array arr[] of N elements, the task is to find the length of the longest non-decreasing subsequence such that the differences between adjacent elements are non-decreasing. For indices i, j, and k:
i < j < k, ai − aj ≤ aj − ak
Examples:
Input: N = 9, arr[] = [1, 3, 5, 4, 7, 8, 10, 6, 9]
Output: 6
Explanation: Longest non-decreasing Subsequence is [1, 3, 5, 7, 8, 10]. Here, the subsequence satisfies the given condition, (3 – 1) <= (5 – 3), (4 – 3) <= (5 – 4), (7 – 5) <= (8 – 7), (8 – 7) <= (10 – 8), and (10 – 8) <= (9 – 6). The length of such Longest Subsequence in this case is 6.Input: N = 8, arr[] = [1, 4, 5, 6, 2, 3, 8, 9]
Output: 5
Explanation: Longest non-decreasing Subsequence with given condition is [1, 4, 6, 8, 9].
Approach: To solve the problem follow the below idea:
The idea is to use a dp array to store the length of such longest subsequence up to index i of the given array. Then, we traverse the array for each index i, and for each index j (0 ≤ j < i), we check if the subsequence [j, i] forms a subsequence. If it does, we update the value of dp[i] with the maximum value of dp[j]+1. Finally, we return the maximum value in the dp array.
Below are the steps for the above approach:
- Initialize a variable say n to store the size of the input array arr.
- Check if the size of the given array is less than or equal to 2, and return the size of the array.
- Initialize an array dp of size n all 0’s.
- Initialize the first two values of the dp to 1 and 2 respectively.
- Initialize a variable say ans = 2.
- Iterate from index i = 2 to i < n,
- Inside the for loop, run another loop from index j = 1 to j < i
- Check if the current element and the previous element form a subsequence with the given condition, if (arr[i] – arr[j] == arr[j] – arr[j-1]),
- Update the dp[] array with the maximum value between the current dp value of i and dp value of j + 1.
- Update the ans variable with the maximum value between itself and the current dp value of i.
- Inside the for loop, run another loop from index j = 1 to j < i
- Return ans.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function that Calculate size for the // array of longest_subsequence for arr int longest_subsequence(vector< int > arr) { int n = arr.size(); // If size is less than or equal to 2, // return size if (n <= 2) return n; // Initialize DP array with all 0's int dp[n]; memset (dp, 0, sizeof (dp)); // Initialize first two values // of DP array dp[0] = 1; dp[1] = 2; // Initialize answer with 2 int ans = 2; // Iterate from index 2 to n-1 for ( int i = 2; i < n; i++) { // Iterate from index 1 to i-1 for ( int j = 1; j < i; j++) { // If current element and // previous element form // a subsequence if (arr[i] - arr[j] == arr[j] - arr[j - 1]) // Update DP array dp[i] = max(dp[i], dp[j] + 1); } // Update answer ans = max(ans, dp[i]); } // Return answer return ans; } // Driver Code int main() { vector< int > arr = { 1, 2, 3, 5, 6, 8 }; // Function Call cout << "Longest Subsequence: " << longest_subsequence(arr) << endl; return 0; } |
Java
// Java program of Longest Convex Subsequence using Dynamic programming import java.util.Arrays; // Function that returns length of longest_convex_subsequence for arr public class LongestConvexSubsequence { public static int longestConvexSubsequence( int [] arr) { int n = arr.length; // If size is less than or equal to 2, return size if (n <= 2 ) return n; // Dynamic Programming table initialization int [] dp = new int [n]; Arrays.fill(dp, 2 ); // Loop to fill the DP table int ans = 2 ; for ( int i = 2 ; i < n; i++) { for ( int j = 1 ; j < i; j++) { // Check if current subsequence is convex if (arr[i] - arr[j] == arr[j] - arr[j - 1 ]) dp[i] = Math.max(dp[i], dp[j] + 1 ); } ans = Math.max(ans, dp[i]); } return ans; } // Driver Code public static void main(String[] args) { int [] arr = { 1 , 2 , 3 , 5 , 6 , 8 }; System.out.println( "Longest Convex Subsequence: " + longestConvexSubsequence(arr)); } } |
Python3
# Python program of Longest Convex Subsequence using Dynamic programming # Function that returns length of longest_convex_subsequence for arr def longest_convex_subsequence(arr): n = len (arr) if n < = 2 : return n # Initialize dp array with all elements as 2 dp = [ 2 ] * n # Initialize answer as 2 (minimum length of a convex subsequence) ans = 2 # Iterate over the array from index 2 to n-1 for i in range ( 2 , n): # Iterate over the array from index 1 to i-1 for j in range ( 1 , i): # Check if the sequence arr[j:i + 1] is convex if arr[i] - arr[j] = = arr[j] - arr[j - 1 ]: # Update the length of the longest convex subsequence ending at index i dp[i] = max (dp[i], dp[j] + 1 ) # Update the answer if necessary ans = max (ans, dp[i]) return ans # Driver Code arr = [ 1 , 2 , 3 , 5 , 6 , 8 ] print ( "Longest Convex Subsequence: " , longest_convex_subsequence(arr)) |
C#
using System; using System.Collections.Generic; class Program { static int LongestSubsequence(List< int > arr) { int n = arr.Count; // If size is less than or equal to 2, // return size if (n <= 2) return n; // Initialize DP array with all 0's int [] dp = new int [n]; // Initialize first two values of DP array dp[0] = 1; dp[1] = 2; // Initialize answer with 2 int ans = 2; // Iterate from index 2 to n-1 for ( int i = 2; i < n; i++) { // Iterate from index 1 to i-1 for ( int j = 1; j < i; j++) { // If current element and previous element form // a subsequence if (arr[i] - arr[j] == arr[j] - arr[j - 1]) { // Update DP array dp[i] = Math.Max(dp[i], dp[j] + 1); } } // Update answer ans = Math.Max(ans, dp[i]); } // Return answer return ans; } static void Main() { List< int > arr = new List< int > { 1, 2, 3, 5, 6, 8 }; // Function Call Console.WriteLine( "Longest Subsequence: " + LongestSubsequence(arr)); } } |
Javascript
// Function that returns length of longest_convex_subsequence for arr function longestSubsequence(arr) { const n = arr.length; // If size is less than or equal to 2, // return size if (n <= 2) { return n; } // Initialize DP array with all 0's const dp = Array(n).fill(0); // Initialize first two values // of DP array dp[0] = 1; dp[1] = 2; // Initialize answer with 2 let ans = 2; // Iterate from index 2 to n-1 for (let i = 2; i < n; i++) { // Iterate from index 1 to i-1 for (let j = 1; j < i; j++) { // If current element and // previous element form // a subsequence if (arr[i] - arr[j] === arr[j] - arr[j - 1]) { // Update DP array dp[i] = Math.max(dp[i], dp[j] + 1); } } // Update answer ans = Math.max(ans, dp[i]); } // Return answer return ans; } // Driver Code const arr = [1, 2, 3, 5, 6, 8]; console.log( "Longest Subsequence:" , longestSubsequence(arr)); //Contributed by Aditi Tyagi |
Longest Subsequence: 3
Time Complexity: O(n2)
Auxiliary Space: O(n), where n is the length of the given array.
Greedy Approach: To solve the problem follow the below idea:
The idea is to use a variable ‘len’ to store the length of the longest subsequence seen so far, and another variable ‘curr_len’ to store the length of the current subsequence. Also, use a variable ‘diff’ to store the difference between two consecutive elements of the current subsequence. Initialize ‘len’ and ‘curr_len’ with 2, as any two elements form a subsequence. Traverse the array and check if the difference between two consecutive elements is the same as the ‘diff’ variable, increment ‘curr_len’, else, update the ‘len’ variable with the maximum value between ‘len’ and ‘curr_len’, and reset ‘curr_len’ to 2, and ‘diff’ to the difference between the two consecutive elements. Return the maximum value between ‘len’ and ‘curr_len’.
Below are the steps for the above approach:
- Initialize a variable say n to store the size of the input array arr.
- Check if the size of the given array is less than or equal to 2, and return the size of the array.
- Initialize a variable len = 2, as the length of the smallest subsequence, is 2.
- Initialize a variable diff to the difference between the second and the first elements of the input array arr.
- Initialize the current length of subsequence as 2, curr_len = 2.
- Traverse the array from index i = 2 to i < n and check if the difference between the current element and the previous element is the same as the difference between the previous two elements, increment curr_length by 1.
- Else if the difference between the current element and the previous element is not the same as the difference between the previous two elements, update the difference between the consecutive elements, diff = arr[i] – arr[i-1].
- Update length of longest subsequence, len = max(len, curr_len).
- The current length of the subsequence is reset to 2.
- Once the for loop completes, the length of the longest subsequence is updated by taking the maximum value between itself and the current length of the subsequence, len = max(len, curr_len).
- Return the value of variable len.
Below is the implementation for the above approach:
C++
// C++ program of Longest non-decreasing // Subsequence using Greedy Approach #include <bits/stdc++.h> using namespace std; // Function that returns length of // longest_subsequence for arr int longest_subsequence(vector< int > arr) { int n = arr.size(); // If the length of the array is less // than or equal to 2, then all // elements are part of non-decreasing // subsequence. if (n <= 2) return n; // Initialize length of longest // non-decreasing subsequence as 2 int len = 2; // Initialize difference of // consecutive elements int diff = arr[1] - arr[0]; // Initialize current length of // subsequence as 2 int curr_len = 2; // Traverse the array for ( int i = 2; i < n; i++) { // If the difference between the // current element and the // previous element is same as the // difference between the // previous two elements if (arr[i] - arr[i - 1] == diff) { // Increment current length of // subsequence curr_len++; } else { // Update the difference // between the consecutive // elements diff = arr[i] - arr[i - 1]; // Update length of longest // non-decreasing subsequence len = max(len, curr_len); // Reset current length of // non-decreasing subsequence // to 2 curr_len = 2; } } // Update length of longest // subsequence len = max(len, curr_len); // Return length of longest // non-decreasing subsequence return len; } // Driver code int main() { vector< int > arr = { 1, 2, 3, 5, 6, 8 }; // Drivers code cout << "Longest non-decreasing Subsequence: " << longest_subsequence(arr) << endl; return 0; } |
Java
// Java program of Longest Convex Subsequence using Greedy Approach import java.util.Arrays; // Function that returns length of longest_convex_subsequence for arr public class LongestConvexSubsequence { public static int longestConvexSubsequence( int [] arr) { int n = arr.length; // If the size of arr is less than or equal to 2, then the length of the longest convex subsequence is n. if (n <= 2 ) return n; // Initialize variables int len = 2 ; // Length of the longest convex subsequence found so far int diff = arr[ 1 ] - arr[ 0 ]; // Difference between the first two elements in the array int curr_len = 2 ; // Current length of the convex subsequence being checked // Loop through the array for ( int i = 2 ; i < n; i++) { // If the difference between the current element and the previous element is the same as the difference between the previous two elements, then the current element is part of the same convex subsequence if (arr[i] - arr[i - 1 ] == diff) { curr_len++; } else { // If the difference is different, then we have found the end of the current convex subsequence diff = arr[i] - arr[i - 1 ]; // Update the difference len = Math.max(len, curr_len); // Update the length of the longest convex subsequence found so far curr_len = 2 ; // Start counting a new convex subsequence } } len = Math.max(len, curr_len); // Check the last convex subsequence return len; // Return the length of the longest convex subsequence } // Driver Code public static void main(String[] args) { int [] arr = { 1 , 2 , 3 , 5 , 6 , 8 }; System.out.println( "Longest Convex Subsequence: " + longestConvexSubsequence(arr)); } } |
Python3
# Python program for Longest Convex Subsequence using Greedy Approach # Function that returns length of longest_convex_subsequence def longest_convex_subsequence(arr): n = len (arr) # if the length of the array is less than or equal to 2, return the length of the array if n < = 2 : return n # initialize the length of longest convex subsequence to 2 max_len = 2 # initialize the difference between the second and first element of the array diff = arr[ 1 ] - arr[ 0 ] # initialize the current length of the convex subsequence to 2 curr_len = 2 # loop through the array starting from the third element for i in range ( 2 , n): # if the difference between current and previous element is same as the difference between previous and second previous element if arr[i] - arr[i - 1 ] = = diff: # increment the current length of the convex subsequence curr_len + = 1 # else the difference between the elements is not same as the difference between previous and second previous element else : # update the difference between the elements diff = arr[i] - arr[i - 1 ] # update the maximum length of convex subsequence with the current length if it is greater max_len = max (max_len, curr_len) # reset the current length to 2 curr_len = 2 # update the maximum length of convex subsequence with the current length if it is greater max_len = max (max_len, curr_len) # return the maximum length of convex subsequence return max_len # Driver Code arr = [ 1 , 2 , 3 , 5 , 6 , 8 ] # print the length of longest convex subsequence of the array print ( "Longest Convex Subsequence: " , longest_convex_subsequence(arr)) |
C#
// C# program of Longest Convex Subsequence using Greedy // Approach using System; using System.Collections.Generic; class Program { static void Main( string [] args) { int [] arr = { 1, 2, 3, 5, 6, 8 }; Console.WriteLine( "Longest Convex Subsequence: " + longestConvexSubsequence(arr)); } // Function that returns length of // longest_convex_subsequence for arr public static int longestConvexSubsequence( int [] arr) { int n = arr.Length; // If the size of arr is less than or equal to 2, // then the length of the longest convex subsequence // is n. if (n <= 2) return n; // Initialize variables int len = 2; // Length of the longest convex // subsequence found so far int diff = arr[1] - arr[0]; // Difference between the first // two elements in the array int curr_len = 2; // Current length of the convex // subsequence being checked // Loop through the array for ( int i = 2; i < n; i++) { // If the difference between the current element // and the previous element is the same as the // difference between the previous two elements, // then the current element is part of the same // convex subsequence if (arr[i] - arr[i - 1] == diff) { curr_len++; } else { // If the difference is different, then we // have found the end of the current convex // subsequence diff = arr[i] - arr[i - 1]; // Update the difference len = Math.Max( len, curr_len); // Update the length of the // longest convex subsequence // found so far curr_len = 2; // Start counting a new convex // subsequence } } len = Math.Max( len, curr_len); // Check the last convex subsequence return len; // Return the length of the longest // convex subsequence } } // This code is contributed by Tapesh(tapeshdua420) |
Javascript
// Function that returns length of // longest_subsequence for arr function longest_subsequence(arr) { let n = arr.length; // If the length of the array is less // than or equal to 2, then all // elements are part of non-decreasing // subsequence. if (n <= 2) return n; // Initialize length of longest // non-decreasing subsequence as 2 let len = 2; // Initialize difference of // consecutive elements let diff = arr[1] - arr[0]; // Initialize current length of // subsequence as 2 let curr_len = 2; // Traverse the array for (let i = 2; i < n; i++) { // If the difference between the // current element and the // previous element is same as the // difference between the // previous two elements if (arr[i] - arr[i - 1] == diff) { // Increment current length of // subsequence curr_len++; } else { // Update the difference // between the consecutive // elements diff = arr[i] - arr[i - 1]; // Update length of longest // non-decreasing subsequence len = Math.max(len, curr_len); // Reset current length of // non-decreasing subsequence // to 2 curr_len = 2; } } // Update length of longest // subsequence len = Math.max(len, curr_len); // Return length of longest // non-decreasing subsequence return len; } // Driver code let arr = [1, 2, 3, 5, 6, 8]; console.log( "Longest non-decreasing Subsequence: " + longest_subsequence(arr)); |
Longest non-decreasing Subsequence: 3
Time Complexity: O(n), where n is the length of the given array.
Auxiliary Space: O(1), since we are not using any additional data structures.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!