Given an array a of size N. The task is to merge all elements in the array and find the maximum possible value. One can merge two elements in the array as explained below.
If i and j are two indexes of the array(i ≠ j). Merging jth element into ith element makes a[i] as a[i] – a[j] and remove a[j] from the array.
Examples:
Input : a[] = {2 1 2 1} (n == 4)
Output : 4
Merge 3rd element into 2nd element then the array becomes {2, -1, 1}
Merge 3rd element into 2nd element then the array becomes {2, -2}
Merge 2nd element into 1st element then the array becomes {4}
Input: a[] = {1, 3, 5, -2, -6}
Output: 17
Merge 4th element into 3rd element then the array becomes {1, 3, -7, -6}
Merge 2nd element into 3rd element then the array becomes {1, -10, -6}
Merge 2nd element into 1st element then the array becomes {11, -6}
Merge 2nd element into 1st element then the array becomes {17}
Approach:
- If the array contains both positive and negative elements, then add absolute value all elements of the array
- If the array contains the only positive elements. Then subtract the least element from the summation of all other elements
- If the array contains the only negative elements. First, replace all elements with their absolute values. Then subtract the least element from the summation of all other elements
Below is the implementation of the above approach:
C++
// CPP program to maximum value after // merging all elements in the array#include <bits/stdc++.h>using namespace std;// Function to maximum value after // merging all elements in the arrayint Max_sum(int a[], int n){ // To check if positive and negative // elements present or not int pos = 0, neg = 0; for(int i = 0; i < n; i++) { // Check for positive integer if(a[i] > 0) pos = 1; // Check for negative integer else if(a[i] < 0) neg = 1; // If both positive and negative // elements are present if(pos == 1 and neg == 1) break; } // To store maximum value possible int sum = 0; if(pos==1 and neg==1) { for(int i=0; i < n ; i++) sum += abs(a[i]); } else if(pos == 1) { // To find minimum value int mini = a[0]; sum = a[0]; for(int i=1; i < n; i++) { mini = min(mini, a[i]); sum += a[i]; } // Remove minimum element sum -= 2*mini; } else if(neg == 1) { // Replace with absolute values for(int i = 0; i < n; i++) a[i] = abs(a[i]); // To find minimum value int mini = a[0]; sum = a[0]; for(int i=1; i < n; i++) { mini = min(mini, a[i]); sum += a[i]; } // Remove minimum element sum -= 2*mini; } // Return the required sum return sum;}// Driver codeint main(){ int a[] = {1, 3, 5, -2, -6}; int n = sizeof(a) / sizeof(a[0]); // Function call cout << Max_sum(a, n); return 0;} |
Java
// Java program to maximum value after // merging all elements in the arrayimport java.io.*;class GFG { // Function to maximum value after // merging all elements in the arraystatic int Max_sum(int a[], int n){ // To check if positive and negative // elements present or not int pos = 0, neg = 0; for(int i = 0; i < n; i++) { // Check for positive integer if(a[i] > 0) pos = 1; // Check for negative integer else if(a[i] < 0) neg = 1; // If both positive and negative // elements are present if((pos == 1) && (neg == 1)) break; } // To store maximum value possible int sum = 0; if((pos == 1) && (neg == 1)) { for(int i = 0; i < n ; i++) sum += Math.abs(a[i]); } else if(pos == 1) { // To find minimum value int mini = a[0]; sum = a[0]; for(int i = 1; i < n; i++) { mini = Math.min(mini, a[i]); sum += a[i]; } // Remove minimum element sum -= 2*mini; } else if(neg == 1) { // Replace with absolute values for(int i = 0; i < n; i++) a[i] = Math.abs(a[i]); // To find minimum value int mini = a[0]; sum = a[0]; for(int i = 1; i < n; i++) { mini = Math.min(mini, a[i]); sum += a[i]; } // Remove minimum element sum -= 2*mini; } // Return the required sum return sum;}// Driver codepublic static void main (String[] args){ int []a = {1, 3, 5, -2, -6}; int n = a.length; // Function call System.out.println (Max_sum(a, n));}}// This code is contributed by ajit. |
Python3
# Python 3 program to maximum value after # merging all elements in the array# Function to maximum value after # merging all elements in the arraydef Max_sum(a, n): # To check if positive and negative # elements present or not pos = 0 neg = 0 for i in range(n): # Check for positive integer if(a[i] > 0): pos = 1 # Check for negative integer elif(a[i] < 0): neg = 1 # If both positive and negative # elements are present if(pos == 1 and neg == 1): break # To store maximum value possible sum = 0 if(pos==1 and neg==1): for i in range(n): sum += abs(a[i]) elif(pos == 1): # To find minimum value mini = a[0] sum = a[0] for i in range(1,n,1): mini = min(mini, a[i]) sum += a[i] # Remove minimum element sum -= 2*mini elif(neg == 1): # Replace with absolute values for i in range(n): a[i] = abs(a[i]) # To find minimum value mini = a[0] sum = a[0] for i in range(1,n): mini = min(mini, a[i]) sum += a[i] # Remove minimum element sum -= 2*mini # Return the required sum return sum# Driver codeif __name__ == '__main__': a = [1, 3, 5, -2, -6] n = len(a) # Function call print(Max_sum(a, n))# This code is contributed by# Surendra_Gangwar |
C#
// C# program to maximum value after // merging all elements in the array using System;class GFG{ // Function to maximum value after // merging all elements in the array static int Max_sum(int[] a, int n) { // To check if positive and negative // elements present or not int pos = 0, neg = 0; for (int i = 0; i < n; i++) { // Check for positive integer if (a[i] > 0) pos = 1; // Check for negative integer else if (a[i] < 0) neg = 1; // If both positive and negative // elements are present if ((pos == 1) && (neg == 1)) break; } // To store maximum value possible int sum = 0; if ((pos == 1) && (neg == 1)) { for (int i = 0; i < n; i++) sum += Math.Abs(a[i]); } else if (pos == 1) { // To find minimum value int mini = a[0]; sum = a[0]; for (int i = 1; i < n; i++) { mini = Math.Min(mini, a[i]); sum += a[i]; } // Remove minimum element sum -= 2 * mini; } else if (neg == 1) { // Replace with absolute values for (int i = 0; i < n; i++) a[i] = Math.Abs(a[i]); // To find minimum value int mini = a[0]; sum = a[0]; for (int i = 1; i < n; i++) { mini = Math.Min(mini, a[i]); sum += a[i]; } // Remove minimum element sum -= 2 * mini; } // Return the required sum return sum; } // Driver code public static void Main(String[] args) { int[] a = { 1, 3, 5, -2, -6 }; int n = a.Length; // Function call Console.WriteLine(Max_sum(a, n)); }}// This code is contributed by// sanjeev2552 |
Javascript
<script>// Javascript program to maximum value after // merging all elements in the array// Function to maximum value after // merging all elements in the arrayfunction Max_sum(a, n){ // To check if positive and negative // elements present or not let pos = 0, neg = 0; for(let i = 0; i < n; i++) { // Check for positive integer if(a[i] > 0) pos = 1; // Check for negative integer else if(a[i] < 0) neg = 1; // If both positive and negative // elements are present if(pos == 1 && neg == 1) break; } // To store maximum value possible let sum = 0; if(pos==1 && neg==1) { for(let i=0; i < n ; i++) sum += Math.abs(a[i]); } else if(pos == 1) { // To find minimum value let mini = a[0]; sum = a[0]; for(let i=1; i < n; i++) { mini = Math.min(mini, a[i]); sum += a[i]; } // Remove minimum element sum -= 2*mini; } else if(neg == 1) { // Replace with absolute values for(let i = 0; i < n; i++) a[i] = Math.abs(a[i]); // To find minimum value let mini = a[0]; sum = a[0]; for(let i=1; i < n; i++) { mini = Math.min(mini, a[i]); sum += a[i]; } // Remove minimum element sum -= 2*mini; } // Return the required sum return sum;}// Driver code let a = [1, 3, 5, -2, -6]; let n = a.length; // Function call document.write(Max_sum(a, n));</script> |
Output:
17
Time Complexity: O(n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!