text: Longest subsequence from an array of pairs having first element increasing and second element decreasing . | C ++ program for the above approach ; Function to find the length of the longest subsequence of pairs whose first element is increasing and second is decreasing ; dp [ i ] : Stores the longest subsequence upto i ; Base case ; When the conditions hold ; Finally , print the required answer ; Driver Code ; Given Input ; Function Call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void longestSubSequence ( pair < int , int > A [ ] , int N ) { int dp [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { dp [ i ] = 1 ; for ( int j = 0 ; j < i ; j ++ ) { if ( A [ j ] . first < A [ i ] . first && A [ j ] . second > A [ i ] . second ) { dp [ i ] = max ( dp [ i ] , dp [ j ] + 1 ) ; } } } cout << dp [ N - 1 ] << endl ; } int main ( ) { pair < int , int > A [ ] = { { 1 , 2 } , { 2 , 2 } , { 3 , 1 } } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; longestSubSequence ( A , N ) ; return 0 ; }