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.
Examples :
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:
C++
// 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; } |
Java
// Java program to get the maximum // sum of the array. import java.io.*; import java.math.*; class GFG { // function to find maximum sum static int maxSum( int arr[], int n) { int neg = 0 , sum = 0 , m = 100000000 , max_sum; // step 1 for ( int i = 0 ; i < 2 * n - 1 ; i++) { // step 2 if (arr[i] < 0 ) neg += 1 ; // step 3 sum += Math.abs(arr[i]); // step 4 m = Math.min(m, Math.abs(arr[i])); } // step 5 if (neg % 2 == 1 && n % 2 == 0 ) { max_sum = sum -= 2 * m; return (max_sum); } max_sum = sum; return (max_sum); } // Driver Function public static void main(String args[]) { int arr[] = {- 1 , - 100 , - 1 }; int n = 2 ; System.out.println(maxSum(arr, n)); } } /*This code is contributed by Nikita Tiwari.*/ |
Python3
# Python3 code to get the maximum # sum of the array. import sys # function to find maximum sum def maxSum (arr, n): neg = 0 sum = 0 m = sys.maxsize # step 1 for i in range ( 2 * n - 1 ): # 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 and n % 2 = = 0 : max_sum = sum - 2 * m return (max_sum) max_sum = sum return max_sum # Driver Code arr = [ - 1 , - 100 , - 1 ] n = 2 print ( maxSum(arr, n)) # This code is contributed by "Sharad_Bhardwaj". |
C#
// C# program to get the maximum // sum of the array. using System; class GFG { // function to find maximum sum static int maxSum( int []arr, int n) { int neg = 0, sum = 0; int m = 100000000, max_sum; // step 1 for ( int i = 0; i < 2 * n - 1; i++) { // step 2 if (arr[i] < 0) neg += 1; // step 3 sum += Math.Abs(arr[i]); // step 4 m = Math.Min(m, Math.Abs(arr[i])); } // step 5 if (neg % 2 == 1 && n % 2 == 0) { max_sum = sum -= 2 * m; return (max_sum); } max_sum = sum; return (max_sum); } // Driver Code public static void Main() { int []arr = {-1, -100, -1}; int n = 2; Console.WriteLine(maxSum(arr, n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to get the // maximum sum of the array. // function to find maximum sum function maxSum( $arr , $n ) { $neg = 0; $sum = 0; $m = PHP_INT_MAX; $max_sum ; // step 1 for ( $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 Code $arr = array (-1, -100, -1); $n = 2; echo maxSum( $arr , $n ) ; // This code is contributed by anuj_67 ?> |
Javascript
<script> // Javascript program to get the maximum // sum of the array. // function to find maximum sum function maxSum(arr, n) { let neg = 0, sum = 0, m = Number.MAX_VALUE, max_sum; // step 1 for (let i = 0; i < 2 * n - 1; i++) { // step 2 neg += (arr[i] < 0); // step 3 sum += Math.abs(arr[i]); // step 4 m = Math.min(m, Math.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); } let arr = [ -1, -100, -1 ]; let n = 2; document.write(maxSum(arr, n)); // This code is contributed by divyeshrabadiya07. </script> |
Output
100
Time Complexity: O(n)
Auxiliary Space: O(1)
Contact Us