Longest increasing subsequence which forms a subarray in the sorted representation of the array | C ++ program to implement the above approach ; Function to find the length of the longest increasing sorted sequence ; Stores the count of all elements ; Store the original array ; Sort the array ; If adjacent element are not same ; Increment count ; Store frequency of each element ; Initialize a DP array ; Iterate over the array ar [ ] ; Length of the longest increasing sorted sequence ; Iterate over the array ; Current element ; If the element has been encountered the first time ; If all the x - 1 previous elements have already appeared ; Otherwise ; If all x - 1 elements have already been encountered ; Increment the count of the current element ; Update maximum subsequence size ; Return the maximum subsequence size ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int LongestSequence ( int a [ ] , int n ) { map < int , int > m ; int ar [ n + 1 ] , i , j ; for ( i = 1 ; i <= n ; i ++ ) { ar [ i ] = a [ i - 1 ] ; } sort ( a , a + n ) ; int c = 1 ; m [ a [ 0 ] ] = c ; for ( i = 1 ; i <= n ; i ++ ) { if ( a [ i ] != a [ i - 1 ] ) { c ++ ; m [ a [ i ] ] = c ; } } map < int , int > cnt ; int dp [ n + 1 ] [ 3 ] = { 0 } ; cnt [ 0 ] = 0 ; for ( i = 1 ; i <= n ; i ++ ) { ar [ i ] = m [ ar [ i ] ] ; cnt [ ar [ i ] ] ++ ; } int ans = 0 , x ; for ( i = 1 ; i <= n ; i ++ ) { x = ar [ i ] ; if ( dp [ x ] [ 0 ] == 0 ) { if ( dp [ x - 1 ] [ 0 ] == cnt [ x - 1 ] ) { dp [ x ] [ 1 ] = dp [ x - 1 ] [ 1 ] ; dp [ x ] [ 2 ] = dp [ x - 1 ] [ 1 ] ; } else { dp [ x ] [ 1 ] = dp [ x - 1 ] [ 0 ] ; } } dp [ x ] [ 2 ] = max ( dp [ x - 1 ] [ 0 ] , dp [ x ] [ 2 ] ) ; if ( dp [ x - 1 ] [ 0 ] == cnt [ x - 1 ] ) { dp [ x ] [ 2 ] = max ( dp [ x ] [ 2 ] , dp [ x - 1 ] [ 1 ] ) ; } for ( j = 0 ; j < 3 ; j ++ ) { dp [ x ] [ j ] ++ ; ans = max ( ans , dp [ x ] [ j ] ) ; } } return ans ; } int main ( ) { int arr [ ] = { 2 , 6 , 4 , 8 , 2 , 9 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << LongestSequence ( arr , N ) ; return 0 ; }