Maximum sum of values in a given range of an Array for Q queries when shuffling is allowed | Java 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
import java . util . * ; import java . lang . * ; class GFG { static int maximumSubarraySum ( int a [ ] , int n , ArrayList < List < Integer > > subarrays ) { int i , maxsum = 0 ; int [ ] prefixArray = new int [ n ] ; for ( i = 0 ; i < subarrays . size ( ) ; ++ i ) { prefixArray [ subarrays . get ( i ) . get ( 0 ) - 1 ] ++ ; prefixArray [ subarrays . get ( i ) . get ( 1 ) ] -- ; } for ( i = 1 ; i < n ; i ++ ) { prefixArray [ i ] += prefixArray [ i - 1 ] ; } Arrays . sort ( prefixArray ) ; Arrays . sort ( a ) ; for ( i = 0 ; i < n ; i ++ ) maxsum += a [ i ] * prefixArray [ i ] ; return maxsum ; } public static void main ( String [ ] args ) { int n = 6 ; int a [ ] = { 4 , 1 , 2 , 1 , 9 , 2 } ; ArrayList < List < Integer > > subarrays = new ArrayList < > ( ) ; subarrays . add ( Arrays . asList ( 1 , 2 ) ) ; subarrays . add ( Arrays . asList ( 1 , 3 ) ) ; subarrays . add ( Arrays . asList ( 1 , 4 ) ) ; subarrays . add ( Arrays . asList ( 3 , 4 ) ) ; System . out . println ( maximumSubarraySum ( a , n , subarrays ) ) ; } }