Maximum possible sub | 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
def SubarraySum ( a , n , x ) : NEW_LINE INDENT ans = - 10000 NEW_LINE for i in range ( n ) : NEW_LINE for j in range ( i , n ) : NEW_LINE INDENT curans = 0 NEW_LINE pq = [ ] NEW_LINE pq2 = [ ] NEW_LINE for k in range ( n ) : NEW_LINE if ( k >= i and k <= j ) : NEW_LINE INDENT curans += a [ k ] NEW_LINE pq2 . append ( a [ k ] ) NEW_LINE DEDENT else : NEW_LINE INDENT pq . append ( a [ k ] ) NEW_LINE DEDENT pq . sort ( ) NEW_LINE pq . reverse ( ) NEW_LINE pq2 . sort ( ) NEW_LINE ans = max ( ans , curans ) NEW_LINE for k in range ( 1 , x + 1 ) : NEW_LINE if ( len ( pq ) == 0 or len ( pq2 ) == 0 or pq2 [ 0 ] >= pq [ 0 ] ) : NEW_LINE INDENT break NEW_LINE DEDENT curans -= pq2 [ 0 ] NEW_LINE pq2 . pop ( 0 ) NEW_LINE curans += pq [ 0 ] NEW_LINE pq . pop ( 0 ) NEW_LINE ans = max ( ans , curans ) NEW_LINE DEDENT return ans NEW_LINE DEDENT a = [ 5 , - 1 , 2 , 3 , 4 , - 2 , 5 ] NEW_LINE x = 2 ; NEW_LINE n = len ( a ) NEW_LINE print ( SubarraySum ( a , n , x ) ) NEW_LINE