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
def maximumSubarraySum ( a , n , subarrays ) : NEW_LINE INDENT maxsum = 0 NEW_LINE prefixArray = [ 0 ] * n NEW_LINE for i in range ( len ( subarrays ) ) : NEW_LINE INDENT prefixArray [ subarrays [ i ] [ 0 ] - 1 ] += 1 NEW_LINE prefixArray [ subarrays [ i ] [ 1 ] ] -= 1 NEW_LINE DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT prefixArray [ i ] += prefixArray [ i - 1 ] NEW_LINE DEDENT prefixArray . sort ( ) NEW_LINE prefixArray . reverse ( ) NEW_LINE a . sort ( ) NEW_LINE a . reverse ( ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT maxsum += a [ i ] * prefixArray [ i ] NEW_LINE DEDENT return maxsum NEW_LINE DEDENT n = 6 NEW_LINE a = [ 4 , 1 , 2 , 1 , 9 , 2 ] NEW_LINE subarrays = [ [ 1 , 2 ] , [ 1 , 3 ] , [ 1 , 4 ] , [ 3 , 4 ] ] NEW_LINE print ( maximumSubarraySum ( a , n , subarrays ) ) NEW_LINE