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

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar