Minimum concatenation required to get strictly LIS for array with repetitive elements | Set | C ++ 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 ; 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 program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int LIS ( int arr [ ] , int n ) { map < int , vector < int > > m ; for ( int i = 0 ; i < n ; i ++ ) m [ arr [ i ] ] . push_back ( i ) ; int k = n ; int ans = 0 ; for ( auto it = m . begin ( ) ; it != m . end ( ) ; it ++ ) { if ( it -> second . back ( ) < k ) { k = it -> second [ 0 ] ; ans += 1 ; } else k = * lower_bound ( it -> second . begin ( ) , it -> second . end ( ) , k ) ; } cout << ans << endl ; } int main ( ) { int arr [ ] = { 1 , 3 , 2 , 1 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; LIS ( arr , n ) ; return 0 ; }