Maximum sum of values in a given range of an Array for Q queries when shuffling is allowed | Function to find the maximum sum of all subarrays ; Initialize maxsum and prefixArray ; Find the frequency using prefix Array ; Perform prefix sum ; Sort both arrays to get a greedy result ; Finally multiply largest frequency with largest array element . ; Return the answer ; Driver Code ; Initial Array ; Subarrays ; Function call
function maximumSubarraySum ( a , n , subarrays ) { let i , maxsum = 0 ; let prefixArray = new Array ( n ) ; prefixArray . fill ( 0 ) ; for ( i = 0 ; i < subarrays . length ; ++ i ) { prefixArray [ subarrays [ i ] [ 0 ] - 1 ] ++ ; prefixArray [ subarrays [ i ] [ 1 ] ] -- ; } for ( i = 1 ; i < n ; i ++ ) { prefixArray [ i ] += prefixArray [ i - 1 ] ; } prefixArray . sort ( ) ; a . sort ( ) ; for ( i = 0 ; i < n ; i ++ ) maxsum += a [ i ] * prefixArray [ i ] ; return maxsum ; } let n = 6 ; let a = [ 4 , 1 , 2 , 1 , 9 , 2 ] ; let subarrays = [ ] ; subarrays . push ( [ 1 , 2 ] ) ; subarrays . push ( [ 1 , 3 ] ) ; subarrays . push ( [ 1 , 4 ] ) ; subarrays . push ( [ 3 , 4 ] ) ; document . write ( maximumSubarraySum ( a , n , subarrays ) ) ;