Count subsequences for every array element in which they are the maximum | Function to merge the subarrays arr [ l . . m ] and arr [ m + 1 , . . r ] based on indices [ ] ; If a [ indices [ l ] ] is less than a [ indices [ j ] ] , add indice [ l ] to temp ; Else add indices [ j ] ; Add remaining elements ; Add remainging elements ; Recursive function to divide the array into to parts ; Recursive call for elements before mid ; Recursive call for elements after mid ; Merge the two sorted arrays ; Function to find the number of subsequences for each element ; Sorting the indices according to array arr [ ] ; Array to store output numbers ; Initialize subseq ; B [ i ] is 2 ^ i ; Doubling the subsequences ; Print the final output , array B [ ] ; Driver Code ; Given array ; Given length ; Function call
def merge ( indices , a , l , mid , r ) : NEW_LINE INDENT temp_ind = [ 0 ] * ( r - l + 1 ) NEW_LINE j = mid + 1 NEW_LINE i = 0 NEW_LINE temp_l = l NEW_LINE while ( l <= mid and j <= r ) : NEW_LINE INDENT if ( a [ indices [ l ] ] < a [ indices [ j ] ] ) : NEW_LINE INDENT temp_ind [ i ] = indices [ l ] NEW_LINE i += 1 NEW_LINE l += 1 NEW_LINE DEDENT else : NEW_LINE INDENT temp_ind [ i ] = indices [ j ] NEW_LINE i += 1 NEW_LINE j += 1 NEW_LINE DEDENT DEDENT while ( l <= mid ) : NEW_LINE INDENT temp_ind [ i ] = indices [ l ] NEW_LINE i += 1 NEW_LINE l += 1 NEW_LINE DEDENT while ( j <= r ) : NEW_LINE INDENT temp_ind [ i ] = indices [ j ] NEW_LINE i += 1 NEW_LINE j += 1 NEW_LINE DEDENT for k in range ( i ) : NEW_LINE INDENT indices [ temp_l ] = temp_ind [ k ] NEW_LINE temp_l += 1 NEW_LINE DEDENT DEDENT def divide ( indices , a , l , r ) : NEW_LINE INDENT if ( l >= r ) : NEW_LINE INDENT return NEW_LINE DEDENT mid = l // 2 + r // 2 NEW_LINE divide ( indices , a , l , mid ) NEW_LINE divide ( indices , a , mid + 1 , r ) NEW_LINE merge ( indices , a , l , mid , r ) NEW_LINE DEDENT def noOfSubsequences ( arr , N ) : NEW_LINE INDENT indices = N * [ 0 ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT indices [ i ] = i NEW_LINE DEDENT divide ( indices , arr , 0 , N - 1 ) NEW_LINE B = [ 0 ] * N NEW_LINE subseq = 1 NEW_LINE for i in range ( N ) : NEW_LINE INDENT B [ indices [ i ] ] = subseq NEW_LINE subseq *= 2 NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT print ( B [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 2 , 3 , 1 ] NEW_LINE N = len ( arr ) NEW_LINE noOfSubsequences ( arr , N ) NEW_LINE DEDENT