Maximum possible sub | C ++ implementation of the approach ; Function to return the maximum sub - array sum after at most x swaps ; To store the required answer ; For all possible intervals ; Keep current ans as zero ; To store the integers which are not part of the sub - array currently under consideration ; To store elements which are part of the sub - array currently under consideration ; Create two sets ; Swap at most X elements ; Remove the minimum of the taken elements ; Add maximum of the discarded elements ; Update the answer ; Return the maximized sub - array sum ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int SubarraySum ( int a [ ] , int n , int x ) { int ans = -10000 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i ; j < n ; j ++ ) { int curans = 0 ; priority_queue < int , vector < int > > pq ; priority_queue < int , vector < int > , greater < int > > pq2 ; for ( int k = 0 ; k < n ; k ++ ) { if ( k >= i && k <= j ) { curans += a [ k ] ; pq2 . push ( a [ k ] ) ; } else pq . push ( a [ k ] ) ; } ans = max ( ans , curans ) ; for ( int k = 1 ; k <= x ; k ++ ) { if ( pq . empty ( ) || pq2 . empty ( ) || pq2 . top ( ) >= pq . top ( ) ) break ; curans -= pq2 . top ( ) ; pq2 . pop ( ) ; curans += pq . top ( ) ; pq . pop ( ) ; ans = max ( ans , curans ) ; } } } return ans ; } int main ( ) { int a [ ] = { 5 , -1 , 2 , 3 , 4 , -2 , 5 } , x = 2 ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << SubarraySum ( a , n , x ) ; return 0 ; }