Maximum sum after rearranging the array for K queries | C ++ program to find the maximum sum after rearranging the array for K queries ; Function to find maximum sum after rearranging array elements ; Auxiliary array to find the count of each selected elements ; Finding count of every element to be selected ; Making it to 0 - indexing ; Prefix sum array concept is used to obtain the count array ; Iterating over the count array to get the final array ; Variable to store the maximum sum ; Sorting both the arrays ; Loop to find the maximum sum ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxSumArrangement ( int A [ ] , int R [ ] [ 2 ] , int N , int M ) { int count [ N ] ; memset ( count , 0 , sizeof count ) ; for ( int i = 0 ; i < M ; ++ i ) { int l = R [ i ] [ 0 ] , r = R [ i ] [ 1 ] + 1 ; l -- ; r -- ; count [ l ] ++ ; if ( r < N ) count [ r ] -- ; } for ( int i = 1 ; i < N ; ++ i ) { count [ i ] += count [ i - 1 ] ; } for ( int i = 0 ; i < N ; ++ i ) { cout << count [ i ] ; } int ans = 0 ; sort ( count , count + N ) ; sort ( A , A + N ) ; for ( int i = 0 ; i < N ; ++ i ) { cout << endl << A [ i ] ; } for ( int i = N - 1 ; i >= 0 ; -- i ) { ans += A [ i ] * count [ i ] ; } return ans ; } int main ( ) { int A [ ] = { 2 , 6 , 10 , 1 , 5 , 6 } ; int R [ ] [ 2 ] = { { 1 , 3 } , { 4 , 6 } , { 3 , 4 } } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; int M = sizeof ( R ) / sizeof ( R [ 0 ] ) ; cout << maxSumArrangement ( A , R , N , M ) ; return 0 ; }