Length of the longest subsegment which is UpDown after inserting atmost one integer | Java 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
class GFG { static int f ( int i , int state , int A [ ] , int dp [ ] [ ] , 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 ] ; } } static int maxLenSeq ( int A [ ] , int N ) { int i , j , tmp , y , ans ; int dp [ ] [ ] = new int [ 1000 ] [ 3 ] ; for ( i = 0 ; i < 1000 ; i ++ ) for ( j = 0 ; j < 3 ; j ++ ) dp [ i ] [ j ] = - 1 ; 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 = Math . max ( ans , dp [ i ] [ 1 ] + 1 ) ; else if ( y % 2 == 0 ) { ans = Math . max ( ans , dp [ i ] [ 1 ] + 1 + dp [ i + y ] [ 2 ] ) ; } else if ( y % 2 == 1 ) { ans = Math . max ( ans , dp [ i ] [ 1 ] + 1 + dp [ i + y ] [ 1 ] ) ; } } return ans ; } public static void main ( String [ ] args ) { int A [ ] = { 1 , 10 , 3 , 20 , 25 , 24 } ; int n = A . length ; System . out . println ( maxLenSeq ( A , n ) ) ; } }