Maximize the difference between two subsets of negative numbers in a set, implemented in C

We have an array consisting of positive and negative numbers. The task is to find the maximum difference between a subset of positive numbers and a subset of negative numbers in the array. Since we have subsets of positive and negative numbers, the difference (sum of positive numbers) - (sum of negative numbers) will always be maximum. This is because subtracting negative numbers will add them. Converting all negative numbers to positive numbers and adding all elements of the array will produce the desired result. Let’s see some examples to understand −

Input − Arr[] = { -2, 0, -3, 8, 10, 12, -4 }

Output − Maximum difference between two subsets − 39

Explanation − The sum of the positive subsets {0, 8,10,12} is 30

The sum of the negative subset {-2, -3, -4} is -9

The maximum difference will be 30 - (-9) = 39

Enter − Arr[] = { -5, -15, -3, -2, 10, 20, 15 }

Output − Maximum difference between two subsets− 70

Explanation − The sum of the positive subset {10, 20, 15} is 45

The sum of the negative subset {-5, -15, -3, -2 The sum of } is -25

The maximum difference will be 45 - (-25) = 70

The method of the following program is as follows

• We use a The integer array Arr[]

• is composed of positive and negative numbers. The function subsetDifference(int arr[],int n) is used to find the maximum difference between a subset of negative numbers and positive numbers. It accepts two parameters, one is the array itself and the other is its size n.

• Use variable sum=0 to store the sum of all elements of the array.

• Start from the left and use a for loop to traverse each element of the array (i=0;i

• If the current The element is a negative number (

• Add each element to the sum.

• Return the sum as the largest possible subset difference.

Example

Demonstration

#include <stdio.h>
int subsetDifference(int arr[], int n){
   int sum = 0;
   for (int i = 0; i < n; i++){
      if(arr[i]<0)
         arr[i]=arr[i]*-1;
      sum += arr[i];
   }
   return sum;
}
// Driver Code
int main(){
   int arr[] = { -1, 3, 5, 17, -32, 12 };
   int n = 6;
   printf("Maximized difference between subsets : %d", subsetDifference(arr, n));
   return 0;
}

Output

If we run the above code, the following output will be generated −

Maximized difference between two subsets: 70

The above is the detailed content of Maximize the difference between two subsets of negative numbers in a set, implemented in C. For more information, please follow other related articles on the PHP Chinese website!