# Maximizing array sum with given operation

There is an array consisting of (2 * n – 1) integers. We can change sign of exactly n elements in the array. In other words, we can select exactly n array elements, and multiply each of them by -1. Find the maximum sum of the array.

Example:

```Input : arr[] = 50 50 50
Output : 150
There is no need to change anything.
The sum of elements equals 150
which is maximum.

Input :  arr[] = -1 -100 -1
Output : 100
Change the sign of the first two
elements. Sum of the elements
equal to 100.```

Approach:

Step 1:- Iterate the loop for 2*n-1 times and repeat the steps 2, 3 and 4.
Step 2:- Calculate no. of negative numbers (neg).
Step 3:- Calculate the sum (sum) of the array by taking absolute values of the numbers.
Step 4:- Find the minimum number of the array by taking absolute values of the numbers (min).
Step 5:- Check if the no. of negative numbers is odd and the value of n (given) is even then subtract two times m from the sum and this will be max_sum of the array else, the value of sum will be the max_sum of the array.

Below is the implementation of the above approach:

`// CPP program to get the maximum`
`// sum of the array.`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// function to find maximum sum`
`int` `maxSum(``int` `arr[], ``int` `n)`
`{`
`    ``int` `neg = 0, sum = 0, `
`     ``m = INT_MAX, max_sum;`
`    `
`    ``// step 1`
`    ``for` `(``int` `i = 0; i < 2 * n - 1; i++) {`
`    `
`        ``// step 2`
`        ``neg += (arr[i] < 0);`
`    `
`        ``// step 3`
`        ``sum += ``abs``(arr[i]);`
`    `
`        ``// step 4`
`        ``m = min(m, ``abs``(arr[i]));`
`    ``}`
`    `
`    ``// step 5`
`    ``if` `(neg % 2 && n % 2 == 0) {`
`        ``max_sum = sum -= 2 * m;`
`        ``return` `(max_sum);`
`    ``}`
`    `
`    ``max_sum = sum;`
`    ``return` `(max_sum);`
`}`
`// Driver Function`
`int` `main()`
`{`
`    ``int` `arr[] = { -1, -100, -1 };`
`    ``int` `n = 2;`
`    ``cout << maxSum(arr, n) << endl;`
`    ``return` `0;`
`}`

Output:

```100

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/maximizing-array-sum-with-given-operation/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at