Count subsequences for every array element in which they are the maximum | Java program for the above approach ; 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
import java . util . * ; class GFG { static void merge ( int [ ] indices , int [ ] a , int l , int mid , int r ) { int [ ] temp_ind = new int [ r - l + 1 ] ; int j = mid + 1 ; int i = 0 , temp_l = l , k ; while ( l <= mid && j <= r ) { if ( a [ indices [ l ] ] < a [ indices [ j ] ] ) temp_ind [ i ++ ] = indices [ l ++ ] ; else temp_ind [ i ++ ] = indices [ j ++ ] ; } while ( l <= mid ) temp_ind [ i ++ ] = indices [ l ++ ] ; while ( j <= r ) temp_ind [ i ++ ] = indices [ j ++ ] ; for ( k = 0 ; k < i ; k ++ ) indices [ temp_l ++ ] = temp_ind [ k ] ; } static void divide ( int [ ] indices , int [ ] a , int l , int r ) { if ( l >= r ) return ; int mid = l / 2 + r / 2 ; divide ( indices , a , l , mid ) ; divide ( indices , a , mid + 1 , r ) ; merge ( indices , a , l , mid , r ) ; } static void noOfSubsequences ( int arr [ ] , int N ) { int [ ] indices = new int [ N ] ; int i ; for ( i = 0 ; i < N ; i ++ ) indices [ i ] = i ; divide ( indices , arr , 0 , N - 1 ) ; int [ ] B = new int [ N ] ; int subseq = 1 ; for ( i = 0 ; i < N ; i ++ ) { B [ indices [ i ] ] = subseq ; subseq *= 2 ; } for ( i = 0 ; i < N ; i ++ ) System . out . print ( B [ i ] + " ▁ " ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 3 , 1 } ; int N = arr . length ; noOfSubsequences ( arr , N ) ; } }