Length of the longest subsegment which is UpDown after inserting atmost one integer | 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
def f ( i , state , A , dp , N ) : NEW_LINE INDENT if i >= N : NEW_LINE INDENT return 0 NEW_LINE DEDENT elif dp [ i ] [ state ] != - 1 : NEW_LINE INDENT return dp [ i ] [ state ] NEW_LINE DEDENT else : NEW_LINE INDENT if i == N - 1 : NEW_LINE INDENT dp [ i ] [ state ] = 1 NEW_LINE DEDENT elif state == 1 and A [ i ] > A [ i + 1 ] : NEW_LINE INDENT dp [ i ] [ state ] = 1 NEW_LINE DEDENT elif state == 2 and A [ i ] < A [ i + 1 ] : NEW_LINE INDENT dp [ i ] [ state ] = 1 NEW_LINE DEDENT elif state == 1 and A [ i ] <= A [ i + 1 ] : NEW_LINE INDENT dp [ i ] [ state ] = 1 + f ( i + 1 , 2 , A , dp , N ) NEW_LINE DEDENT elif state == 2 and A [ i ] >= A [ i + 1 ] : NEW_LINE INDENT dp [ i ] [ state ] = 1 + f ( i + 1 , 1 , A , dp , N ) NEW_LINE DEDENT return dp [ i ] [ state ] NEW_LINE DEDENT DEDENT def maxLenSeq ( A , N ) : NEW_LINE INDENT dp = [ [ - 1 , - 1 , - 1 ] for i in range ( 1000 ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT tmp = f ( i , 1 , A , dp , N ) NEW_LINE tmp = f ( i , 2 , A , dp , N ) NEW_LINE DEDENT ans = - 1 NEW_LINE for i in range ( N ) : NEW_LINE INDENT y = dp [ i ] [ 1 ] NEW_LINE if ( i + y ) >= N : NEW_LINE INDENT ans = max ( ans , dp [ i ] [ 1 ] + 1 ) NEW_LINE DEDENT elif y % 2 == 0 : NEW_LINE INDENT ans = max ( ans , dp [ i ] [ 1 ] + 1 + dp [ i + y ] [ 2 ] ) NEW_LINE DEDENT elif y % 2 == 1 : NEW_LINE INDENT ans = max ( ans , dp [ i ] [ 1 ] + 1 + dp [ i + y ] [ 1 ] ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ 1 , 10 , 3 , 20 , 25 , 24 ] NEW_LINE n = len ( A ) NEW_LINE print ( maxLenSeq ( A , n ) ) NEW_LINE DEDENT