Minimum concatenation required to get strictly LIS for array with repetitive elements | Set | Python3 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  <int, vector<int> > m; ; Mapping index with their values in ordered map ; k refers to present minimum index ; Stores the number of concatenation required ; Iterate over map m ; it . second . back refers to the last element of corresponding vector ; find the index of next minimum element in the sequence ; Return the final answer ; Driver code
from bisect import bisect_left NEW_LINE def LIS ( arr , n ) : NEW_LINE INDENT m = { } NEW_LINE for i in range ( n ) : NEW_LINE INDENT m [ arr [ i ] ] = m . get ( arr [ i ] , [ ] ) NEW_LINE m [ arr [ i ] ] . append ( i ) NEW_LINE DEDENT k = n NEW_LINE ans = 1 NEW_LINE for key , value in m . items ( ) : NEW_LINE INDENT if ( value [ len ( value ) - 1 ] < k ) : NEW_LINE INDENT k = value [ 0 ] NEW_LINE ans += 1 NEW_LINE DEDENT else : NEW_LINE INDENT k = bisect_left ( value , k ) NEW_LINE DEDENT DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 3 , 2 , 1 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE LIS ( arr , n ) NEW_LINE DEDENT