Rearrange array elements excluded by given ranges to maximize sum of subarrays starting from the first index | Java program for the above approach ; Function that finds the maximum sum all subarrays from the starting index after rearranging the array ; Stores elements after rearranging ; Keeps track of visited elements ; Traverse the queries ; Mark elements that are not allowed to rearranged ; Stores the indices ; Get indices and elements that are allowed to rearranged ; Store the current index and element ; Sort vector v in descending order ; Insert elements in array ; Stores the resultant sum ; Stores the prefix sums ; Traverse the given array ; Return the maximum sum ; Driver Code ; Given array ; Given size ; Queries ; Number of queries ; Function Call
import java . util . * ; class GFG { static int maxSum ( int n , int a [ ] , int [ ] [ ] l , int q ) { Vector < Integer > v = new Vector < > ( ) ; int [ ] d = new int [ n ] ; for ( int i = 0 ; i < q ; i ++ ) { for ( int x = l [ i ] [ 0 ] ; x <= l [ i ] [ 1 ] ; x ++ ) { if ( d [ x ] == 0 ) { d [ x ] = 1 ; } } } HashSet < Integer > st = new HashSet < > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( d [ i ] == 0 ) { v . add ( a [ i ] ) ; st . add ( i ) ; } } Collections . sort ( v ) ; Collections . reverse ( v ) ; int c = 0 ; for ( int it : st ) { a [ it ] = v . get ( c ) ; c ++ ; } int pref_sum = 0 ; int temp_sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { temp_sum += a [ i ] ; pref_sum += temp_sum ; } return pref_sum ; } public static void main ( String [ ] args ) { int [ ] arr = { - 8 , 4 , - 2 , - 6 , 4 , 7 , 1 } ; int N = arr . length ; int [ ] [ ] q = { { 0 , 0 } , { 4 , 5 } } ; int queries = q . length ; System . out . print ( maxSum ( N , arr , q , queries ) ) ; } }