Minimum concatenation required to get strictly LIS for array with repetitive elements | Set | Java implementation to Find the minimum concatenation required to get strictly Longest Increasing Subsequence for the given array with repetitive elements ; ordered map containing value and a vector containing index of it 's occurrences ; Mapping index with their values in ordered map ; k refers to present minimum index ; Stores the number of concatenation required ; Iterate over map m ; List containing all corresponding indexes ; Find the index of next minimum element in the sequence ; Return the final answer ; Driver code
import java . io . * ; import java . util . * ; class GFG { static void LIS ( int arr [ ] , int n ) { TreeMap < Integer , List < Integer > > m = new TreeMap < Integer , List < Integer > > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { List < Integer > indexes ; if ( m . containsKey ( arr [ i ] ) ) { indexes = m . get ( arr [ i ] ) ; } else { indexes = new ArrayList < Integer > ( ) ; } indexes . add ( i ) ; m . put ( arr [ i ] , indexes ) ; } int k = n ; int ans = 0 ; for ( Map . Entry < Integer , List < Integer > > it : m . entrySet ( ) ) { List < Integer > indexes = it . getValue ( ) ; if ( indexes . get ( indexes . size ( ) - 1 ) < k ) { k = indexes . get ( 0 ) ; ans ++ ; } else k = lower_bound ( indexes , k ) ; } System . out . println ( ans ) ; } static int lower_bound ( List < Integer > indexes , int k ) { int low = 0 , high = indexes . size ( ) - 1 ; while ( low < high ) { int mid = ( low + high ) / 2 ; if ( indexes . get ( mid ) < k ) low = mid + 1 ; else high = mid ; } return indexes . get ( low ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 3 , 2 , 1 , 2 } ; int n = arr . length ; LIS ( arr , n ) ; } }