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
function computeLIS ( circBuff , start , end , n ) { let LIS = new Array ( n + end - start ) ; for ( let i = start ; i < end ; i ++ ) LIS [ i ] = 1 ; for ( let i = start + 1 ; i < end ; i ++ ) for ( let j = start ; j < i ; j ++ ) if ( circBuff [ i ] > circBuff [ j ] && LIS [ i ] < LIS [ j ] + 1 ) LIS [ i ] = LIS [ j ] + 1 ; let res = Number . MIN_VALUE ; for ( let i = start ; i < end ; i ++ ) res = Math . max ( res , LIS [ i ] ) ; return res ; } function LICS ( arr , n ) { let circBuff = new Array ( 2 * n ) ; for ( let i = 0 ; i < n ; i ++ ) circBuff [ i ] = arr [ i ] ; for ( let i = n ; i < 2 * n ; i ++ ) circBuff [ i ] = arr [ i - n ] ; let res = Number . MIN_VALUE ; for ( let i = 0 ; i < n ; i ++ ) res = Math . max ( computeLIS ( circBuff , i , i + n , n ) , res ) ; return res ; } let arr = [ 1 , 4 , 6 , 2 , 3 ] ; document . write ( " " + LICS ( arr , arr . length ) ) ;