Rearrange array elements excluded by given ranges to maximize sum of subarrays starting from the first index | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxSum ( int n , int a [ ] , int l [ ] [ 2 ] , int q ) { vector < int > v ; int d [ n ] = { 0 } ; 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 ; } } } set < int > st ; for ( int i = 0 ; i < n ; i ++ ) { if ( d [ i ] == 0 ) { v . push_back ( a [ i ] ) ; st . insert ( i ) ; } } sort ( v . begin ( ) , v . end ( ) , greater < int > ( ) ) ; int c = 0 ; for ( auto it : st ) { a [ it ] = v ; 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 ; } int main ( ) { int arr [ ] = { -8 , 4 , -2 , -6 , 4 , 7 , 1 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int q [ ] [ 2 ] = { { 0 , 0 } , { 4 , 5 } } ; int queries = sizeof ( q ) / sizeof ( q [ 0 ] ) ; cout << maxSum ( N , arr , q , queries ) ; return 0 ; }