Find the Longest Increasing Subsequence in Circular manner | Utility method to find LIS using Dynamic programming ; Initialize LIS values for all indexes ; Compute optimized LIS values in bottom up manner ; Set j on the basis of current window i . e . first element of the current window ; Pick maximum of all LIS values ; Function to find Longest Increasing subsequence in Circular manner ; Make a copy of given array by appending same array elements to itself ; Perform LIS for each window of size n ; Driver code
def computeLIS ( circBuff , start , end , n ) : NEW_LINE INDENT LIS = [ 0 for i in range ( end ) ] NEW_LINE for i in range ( start , end ) : NEW_LINE INDENT LIS [ i ] = 1 NEW_LINE DEDENT for i in range ( start + 1 , end ) : NEW_LINE INDENT for j in range ( start , i ) : NEW_LINE INDENT if ( circBuff [ i ] > circBuff [ j ] and LIS [ i ] < LIS [ j ] + 1 ) : NEW_LINE INDENT LIS [ i ] = LIS [ j ] + 1 NEW_LINE DEDENT DEDENT DEDENT res = - 100000 NEW_LINE for i in range ( start , end ) : NEW_LINE INDENT res = max ( res , LIS [ i ] ) NEW_LINE DEDENT return res NEW_LINE DEDENT def LICS ( arr , n ) : NEW_LINE INDENT circBuff = [ 0 for i in range ( 2 * n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT circBuff [ i ] = arr [ i ] NEW_LINE DEDENT for i in range ( n , 2 * n ) : NEW_LINE INDENT circBuff [ i ] = arr [ i - n ] NEW_LINE DEDENT res = - 100000 NEW_LINE for i in range ( n ) : NEW_LINE INDENT res = max ( computeLIS ( circBuff , i , i + n , n ) , res ) NEW_LINE DEDENT return res NEW_LINE DEDENT arr = [ 1 , 4 , 6 , 2 , 3 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " Length ▁ of ▁ LICS ▁ is " , LICS ( arr , n ) ) NEW_LINE