Maximum array sum that can be obtained after exactly k changes | C ++ implementation of the approach ; Utility function to return the sum of the array elements ; Function to return the maximized sum of the array after performing the given operation exactly k times ; Sort the array elements ; Change signs of the negative elements starting from the smallest ; If a single operation has to be performed then it must be performed on the smallest positive element ; To store the index of the minimum element ; Update the minimum index ; Perform remaining operation on the smallest element ; Return the sum of the updated array ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int sumArr ( int arr [ ] , int n ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; return sum ; } int maxSum ( int arr [ ] , int n , int k ) { sort ( arr , arr + n ) ; int i = 0 ; while ( i < n && k > 0 && arr [ i ] < 0 ) { arr [ i ] *= -1 ; k -- ; i ++ ; } if ( k % 2 == 1 ) { int min = 0 ; for ( i = 1 ; i < n ; i ++ ) if ( arr [ min ] > arr [ i ] ) min = i ; arr [ min ] *= -1 ; } return sumArr ( arr , n ) ; } int main ( ) { int arr [ ] = { -5 , 4 , 1 , 3 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int k = 4 ; cout << maxSum ( arr , n , k ) << endl ; return 0 ; }