Given an array of pairs A[][] of size N, the task is to find the longest subsequences where the first element is increasing and the second element is decreasing.
Examples:
Input: A[]={{1, 2}, {2, 2}, {3, 1}}, N = 3
Output: 2
Explanation: The longest subsequence satisfying the conditions is of length 2 and consists of {1, 2} and {3, 1};Input: A[] = {{1, 3}, {2, 5}, {3, 2}, {5, 2}, {4, 1}}, N = 5
Output: 3
Naive Approach: The simplest approach is to use Recursion. For every pair in the array, there are two possible choices, i.e. either to include the current pair in the subsequence or not. Therefore, iterate over the array recursively and find the required longest subsequence.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Recursive function to find the length of// the longest subsequence of pairs whose first// element is increasing and second is decreasingint longestSubSequence(pair<int, int> A[], int N, int ind = 0, int lastf = INT_MIN, int lasts = INT_MAX){ // Base case if (ind == N) return 0; // Not include the current pair // in the longest subsequence int ans = longestSubSequence(A, N, ind + 1, lastf, lasts); // Including the current pair // in the longest subsequence if (A[ind].first > lastf && A[ind].second < lasts) ans = max(ans, longestSubSequence(A, N, ind + 1, A[ind].first, A[ind].second) + 1); return ans;}// Driver Codeint main(){ // Given Input pair<int, int> A[] = { { 1, 2 }, { 2, 2 }, { 3, 1 } }; int N = sizeof(A) / sizeof(A[0]); // Function Call cout << longestSubSequence(A, N) << "\n"; return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Recursive function to find the length of// the longest subsequence of pairs whose first// element is increasing and second is decreasingpublic static Integer longestSubSequence(int[][] A, int N, int ind, int lastf, int lasts){ ind = (ind > 0 ? ind : 0); lastf = (lastf > 0 ? lastf: Integer.MIN_VALUE); lasts = (lasts > 0 ? lasts: Integer.MAX_VALUE); // Base case if (ind == N) return 0; // Not include the current pair // in the longest subsequence int ans = longestSubSequence(A, N, ind + 1, lastf, lasts); // Including the current pair // in the longest subsequence if (A[ind][0] > lastf && A[ind][1] < lasts) ans = Math.max(ans, longestSubSequence(A, N, ind + 1, A[ind][0], A[ind][1]) + 1); return ans;}public static int longestSubSequence(int[][] A, int N){ return longestSubSequence(A, N, 0, 0, 0);}// Driver Codepublic static void main(String args[]) { // Given Input int[][] A = { { 1, 2 }, { 2, 2 }, { 3, 1 } }; int N = A.length; // Function Call System.out.println(longestSubSequence(A, N));}}// This code is contributed by _saurabh_jaiswal |
Python3
# Python 3 program for the above approachimport sys# Recursive function to find the length of# the longest subsequence of pairs whose first# element is increasing and second is decreasingdef longestSubSequence(A, N, ind=0, lastf=-sys.maxsize-1, lasts=sys.maxsize): # Base case if (ind == N): return 0 # Not include the current pair # in the longest subsequence ans = longestSubSequence(A, N, ind + 1, lastf, lasts) # Including the current pair # in the longest subsequence if (A[ind][0] > lastf and A[ind][1] < lasts): ans = max(ans, longestSubSequence(A, N, ind + 1, A[ind][0], A[ind][1]) + 1) return ans# Driver Codeif __name__ == "__main__": # Given Input A = [[1, 2], [2, 2], [3, 1]] N = len(A) # Function Call print(longestSubSequence(A, N)) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;class GFG{// Recursive function to find the length of// the longest subsequence of pairs whose first// element is increasing and second is decreasingpublic static int longestSubSequence(int[,] A, int N, int ind, int lastf, int lasts){ ind = (ind > 0 ? ind : 0); lastf = (lastf > 0 ? lastf: Int32.MinValue); lasts = (lasts > 0 ? lasts: Int32.MaxValue); // Base case if (ind == N) return 0; // Not include the current pair // in the longest subsequence int ans = longestSubSequence(A, N, ind + 1, lastf, lasts); // Including the current pair // in the longest subsequence if (A[ind, 0] > lastf && A[ind, 1] < lasts) ans = Math.Max(ans, longestSubSequence(A, N, ind + 1, A[ind, 0], A[ind, 1]) + 1); return ans;}public static int longestSubSequence(int[,] A, int N){ return longestSubSequence(A, N, 0, 0, 0);}// Driver Codepublic static void Main(){ // Given Input int[,] A = { { 1, 2 }, { 2, 2 }, { 3, 1 } }; int N = A.GetLength(0); // Function Call Console.Write(longestSubSequence(A, N));}}// This code is contributed by target_2. |
Javascript
<script>// JavaScript program for the above approach// Function to find the length of the// longest subsequence of pairs whose first// element is increasing and second is decreasingfunction longestSubSequence(A, N){ // dp[i]: Stores the longest // subsequence upto i let dp = new Array(N); for (let i = 0; i < N; i++) { // Base case dp[i] = 1; for (let j = 0; j < i; j++) { // When the conditions hold if (A[j][0] < A[i][0] && A[j][1] > A[i][1]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } // Finally, print the required answer document.write(dp[N - 1] + "<br>");}// Driver Code // Given Input let A = [ [ 1, 2 ], [ 2, 2 ], [ 3, 1 ] ]; let N = A.length; // Function Call longestSubSequence(A, N); </script> |
Output
2
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: This problem has Overlapping Subproblems property and Optimal Substructure property. Therefore, this problem can be solved using Dynamic Programming. Like other typical Dynamic Programming (DP) problems, recomputation of same subproblems can be avoided by constructing a temporary array that stores the results of the subproblems.
Follow the steps below to solve this problem:
- Initialize a dp[] array, where dp[i] stores the length of the longest subsequence that can be formed using elements up to index i.
- Iterate over the range [0, N-1] using variable i:
- Base case: Update dp[i] as 1.
- Iterate over the range [0, i – 1] using a variable j:
- If A[j].first is less than A[i].first and A[j].second is greater than A[i].second, then update dp[i] as maximum of dp[i] and dp[j] + 1.
- Finally, print dp[N-1].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the length of the// longest subsequence of pairs whose first// element is increasing and second is decreasingvoid longestSubSequence(pair<int, int> A[], int N){ // dp[i]: Stores the longest // subsequence upto i int dp[N]; for (int i = 0; i < N; i++) { // Base case dp[i] = 1; for (int j = 0; j < i; j++) { // When the conditions hold if (A[j].first < A[i].first && A[j].second > A[i].second) { dp[i] = max(dp[i], dp[j] + 1); } } } // Finally, print the required answer cout << dp[N - 1] << endl;}// Driver Codeint main(){ // Given Input pair<int, int> A[] = { { 1, 2 }, { 2, 2 }, { 3, 1 } }; int N = sizeof(A) / sizeof(A[0]); // Function Call longestSubSequence(A, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to find the length of the// longest subsequence of pairs whose first// element is increasing and second is decreasingpublic static void longestSubSequence(int[][] A, int N){ // dp[i]: Stores the longest // subsequence upto i int[] dp = new int[N]; for(int i = 0; i < N; i++) { // Base case dp[i] = 1; for(int j = 0; j < i; j++) { // When the conditions hold if (A[j][0] < A[i][0] && A[j][1] > A[i][1]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } // Finally, print the required answer System.out.println(dp[N - 1]);}// Driver Codepublic static void main(String args[]){ // Given Input int[][] A = { { 1, 2 }, { 2, 2 }, { 3, 1 } }; int N = A.length; // Function Call longestSubSequence(A, N);}}// This code is contributed by gfgking |
Python3
# Python3 program for the above approach# Function to find the length of the# longest subsequence of pairs whose first# element is increasing and second is decreasingdef longestSubSequence(A, N): # dp[i]: Stores the longest # subsequence upto i dp = [0]*N for i in range(N): # Base case dp[i] = 1 for j in range(i): # When the conditions hold if (A[j][0] < A[i][0] and A[j][1] > A[i][1]): dp[i] = max(dp[i], dp[j] + 1) # Finally, print the required answer print (dp[N - 1])# Driver Codeif __name__ == '__main__': #Given Input A = [ [ 1, 2 ], [ 2, 2 ], [ 3, 1 ] ] N = len(A) #Function Call longestSubSequence(A, N)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG { // Function to find the length of the // longest subsequence of pairs whose first // element is increasing and second is decreasing static void longestSubSequence(int[,] A, int N) { // dp[i]: Stores the longest // subsequence upto i int[] dp = new int[N]; for(int i = 0; i < N; i++) { // Base case dp[i] = 1; for(int j = 0; j < i; j++) { // When the conditions hold if (A[j,0] < A[i,0] && A[j,1] > A[i,1]) { dp[i] = Math.Max(dp[i], dp[j] + 1); } } } // Finally, print the required answer Console.Write(dp[N - 1]); } static void Main() { // Given Input int[,] A = { { 1, 2 }, { 2, 2 }, { 3, 1 } }; int N = A.GetLength(0); // Function Call longestSubSequence(A, N); }}// This code is contributed by decode2207. |
Javascript
<script>// JavaScript program for the above approach// Function to find the length of the// longest subsequence of pairs whose first// element is increasing and second is decreasingfunction longestSubSequence(A, N) { // dp[i]: Stores the longest // subsequence upto i let dp = new Array(N); for (let i = 0; i < N; i++) { // Base case dp[i] = 1; for (let j = 0; j < i; j++) { // When the conditions hold if (A[j][0] < A[i][0] && A[j][1] > A[i][1]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } // Finally, print the required answer document.write(dp[N - 1] + "<br>");}// Driver Code// Given Inputlet A = [[1, 2],[2, 2],[3, 1]];let N = A.length;// Function CalllongestSubSequence(A, N);</script> |
Output
2
Time Complexity: O(N2)
Auxiliary Space: O(N)
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!
