text: Length of the longest subsegment which is UpDown after inserting atmost one integer | C ++ implementation of the approach ; Function to recursively fill the dp array ; If f ( i , state ) is already calculated then return the value ; Calculate f ( i , state ) according to the recurrence relation and store in dp [ ] [ ] ; Function that calls the resucrsive function to fill the dp array and then returns the result ; dp [ ] [ ] array for storing result of f ( i , 1 ) and f ( 1 , 2 ) ; Populating the array dp [ ] with - 1 ; Make sure that longest UD and DU sequence starting at each index is calculated ; Assume the answer to be - 1 This value will only increase ; y is the length of the longest UD sequence starting at i ; If length is even then add an integer and then a DU sequence starting at i + y ; If length is odd then add an integer and then a UD sequence starting at i + y ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int f ( int i , int state , int A [ ] , int dp [ ] [ 3 ] , int N ) { if ( i >= N ) return 0 ; else if ( dp [ i ] [ state ] != -1 ) { return dp [ i ] [ state ] ; } else { if ( i == N - 1 ) dp [ i ] [ state ] = 1 ; else if ( state == 1 && A [ i ] > A [ i + 1 ] ) dp [ i ] [ state ] = 1 ; else if ( state == 2 && A [ i ] < A [ i + 1 ] ) dp [ i ] [ state ] = 1 ; else if ( state == 1 && A [ i ] <= A [ i + 1 ] ) dp [ i ] [ state ] = 1 + f ( i + 1 , 2 , A , dp , N ) ; else if ( state == 2 && A [ i ] >= A [ i + 1 ] ) dp [ i ] [ state ] = 1 + f ( i + 1 , 1 , A , dp , N ) ; return dp [ i ] [ state ] ; } } int maxLenSeq ( int A [ ] , int N ) { int i , tmp , y , ans ; int dp [ 1000 ] [ 3 ] ; memset ( dp , -1 , sizeof dp ) ; for ( i = 0 ; i < N ; i ++ ) { tmp = f ( i , 1 , A , dp , N ) ; tmp = f ( i , 2 , A , dp , N ) ; } ans = -1 ; for ( i = 0 ; i < N ; i ++ ) { y = dp [ i ] [ 1 ] ; if ( i + y >= N ) ans = max ( ans , dp [ i ] [ 1 ] + 1 ) ; else if ( y % 2 == 0 ) { ans = max ( ans , dp [ i ] [ 1 ] + 1 + dp [ i + y ] [ 2 ] ) ; } else if ( y % 2 == 1 ) { ans = max ( ans , dp [ i ] [ 1 ] + 1 + dp [ i + y ] [ 1 ] ) ; } } return ans ; } int main ( ) { int A [ ] = { 1 , 10 , 3 , 20 , 25 , 24 } ; int n = sizeof ( A ) / sizeof ( int ) ; cout << maxLenSeq ( A , n ) ; return 0 ; }