Maximum possible sub | Java 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 .
import java . io . * ; import java . util . * ; class GFG { static 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 ; ArrayList < Integer > pq = new ArrayList < Integer > ( ) ; ArrayList < Integer > pq2 = new ArrayList < Integer > ( ) ; for ( int k = 0 ; k < n ; k ++ ) { if ( k >= i && k <= j ) { curans += a [ k ] ; pq2 . add ( a [ k ] ) ; } else pq . add ( a [ k ] ) ; } Collections . sort ( pq ) ; Collections . reverse ( pq ) ; Collections . sort ( pq2 ) ; ans = Math . max ( ans , curans ) ; for ( int k = 1 ; k <= x ; k ++ ) { if ( pq . size ( ) == 0 || pq2 . size ( ) == 0 || pq2 . get ( 0 ) >= pq . get ( 0 ) ) break ; curans -= pq2 . get ( 0 ) ; pq2 . remove ( 0 ) ; curans += pq . get ( 0 ) ; pq . remove ( 0 ) ; ans = Math . max ( ans , curans ) ; } } } return ans ; } public static void main ( String [ ] args ) { int [ ] a = { 5 , - 1 , 2 , 3 , 4 , - 2 , 5 } ; int x = 2 ; int n = a . length ; System . out . println ( SubarraySum ( a , n , x ) ) ; } }