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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximumSubarraySum ( int a [ ] , int n , vector < pair < int , int > > & subarrays ) { int i , maxsum = 0 ; int prefixArray [ n ] = { 0 } ; for ( i = 0 ; i < subarrays . size ( ) ; ++ i ) { prefixArray [ subarrays [ i ] . first - 1 ] ++ ; prefixArray [ subarrays [ i ] . second ] -- ; } for ( i = 1 ; i < n ; i ++ ) { prefixArray [ i ] += prefixArray [ i - 1 ] ; } sort ( prefixArray , prefixArray + n , greater < int > ( ) ) ; sort ( a , a + n , greater < int > ( ) ) ; for ( i = 0 ; i < n ; i ++ ) maxsum += a [ i ] * prefixArray [ i ] ; return maxsum ; } int main ( ) { int n = 6 ; int a [ ] = { 4 , 1 , 2 , 1 , 9 , 2 } ; vector < pair < int , int > > subarrays ; subarrays . push_back ( { 1 , 2 } ) ; subarrays . push_back ( { 1 , 3 } ) ; subarrays . push_back ( { 1 , 4 } ) ; subarrays . push_back ( { 3 , 4 } ) ; cout << maximumSubarraySum ( a , n , subarrays ) ; }