Divide given numeric string into at most two increasing subsequences which form an increasing string upon concatenation | C ++ program for the above approach ; Function to check for valid subsequences ; Stores which element belongs to which subsequence ; Check for each pos if a possible subsequence exist or not ; Last member of 1 subsequence ; Last Member of 2 nd subsequence ; Check if current element can go to 2 nd subsequence ; Check if the current elements belongs to first subsequence ; If the current element does not belong to any subsequence ; Check if last digit of first subsequence is greater than pos ; If a subsequence is found , find the subsequences ; Stores the resulting subsequences ; Print the subsequence ; If no subsequence found , print - 1 ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findSubsequence ( string str ) { int n = str . size ( ) ; char res [ n ] ; for ( int i = 0 ; i < n ; i ++ ) res [ i ] = 0 ; for ( int pos = 0 ; pos <= 9 ; pos ++ ) { char lst1 = '0' ; bool flag = 1 ; char lst2 = pos + '0' ; for ( int i = 0 ; i < n ; i ++ ) { if ( lst2 <= str [ i ] ) { res [ i ] = '2' ; lst2 = str [ i ] ; } else if ( lst1 <= str [ i ] ) { res [ i ] = '1' ; lst1 = str [ i ] ; } else flag = 0 ; } if ( lst1 > pos + '0' ) flag = 0 ; if ( flag ) { string S1 = " " ; string S2 = " " ; for ( int i = 0 ; i < n ; i ++ ) { if ( res [ i ] == '1' ) { S1 += str [ i ] ; } else { S2 += str [ i ] ; } } cout << S1 << ' ▁ ' << S2 << endl ; return ; } } cout << " - 1" ; } int main ( ) { string S = "040425524644" ; findSubsequence ( S ) ; S = "123456789" ; findSubsequence ( S ) ; return 0 ; }