Maximum sum of values in a given range of an Array for Q queries when shuffling is allowed | C # implementation to find the maximum sum of K subarrays 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
using System ; using System . Collections . Generic ; class GFG { static int maximumSubarraySum ( int [ ] a , int n , List < List < int > > subarrays ) { int i , maxsum = 0 ; int [ ] prefixArray = new int [ n ] ; for ( i = 0 ; i < subarrays . Count ; ++ i ) { prefixArray [ subarrays [ i ] [ 0 ] - 1 ] ++ ; prefixArray [ subarrays [ i ] [ 1 ] ] -- ; } for ( i = 1 ; i < n ; i ++ ) { prefixArray [ i ] += prefixArray [ i - 1 ] ; } Array . Sort ( prefixArray ) ; Array . Sort ( a ) ; for ( i = 0 ; i < n ; i ++ ) maxsum += a [ i ] * prefixArray [ i ] ; return maxsum ; } static void Main ( ) { int n = 6 ; int [ ] a = { 4 , 1 , 2 , 1 , 9 , 2 } ; List < List < int > > subarrays = new List < List < int > > ( ) ; subarrays . Add ( new List < int > { 1 , 2 } ) ; subarrays . Add ( new List < int > { 1 , 3 } ) ; subarrays . Add ( new List < int > { 1 , 4 } ) ; subarrays . Add ( new List < int > { 3 , 4 } ) ; Console . WriteLine ( maximumSubarraySum ( a , n , subarrays ) ) ; } }