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*n1 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/maximizingarraysumwithgivenoperation/
We have built the accelerating growthoriented 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
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide