Write a program for the maximum possible difference between two subsets of an array.Given an array of n integers. The array may contain repetitive elements, but the highest frequency of any element must not exceed two. Make two subsets such that the difference of the sum of their elements is maximum and both of them jointly contain all elements of the given array along with the most important condition, no subset should contain repetitive elements. ExampleInput:45 8 -1 4Output:Maximum Difference = 18Explanation:Suppose arr[ ] = {5, 8, -1, 4}Let Subset A = {5, 8, 4} & Subset B = {-1}Sum of elements of subset A = 17, of subset B = -1Difference of Sum of Both subsets = 17 - (-1) = 18Input format :The first input line consists of the size of an array, n.The second input consists of the array elements, separated by space.Output format :The output displays the maximum possible difference between two subsets of an array.Refer to the sample output for the formatting specifications.Code constraints :2 ≤ n ≤ 100Sample test cases :Input 1 :74 2 -3 3 -2 -2 8Output 1 :Maximum Difference = 20Input 2 :45 8 -1 4Output 2 :Maximum Difference = 18
Question
Write a program for the maximum possible difference between two subsets of an array.Given an array of n integers. The array may contain repetitive elements, but the highest frequency of any element must not exceed two. Make two subsets such that the difference of the sum of their elements is maximum and both of them jointly contain all elements of the given array along with the most important condition, no subset should contain repetitive elements. ExampleInput:45 8 -1 4Output:Maximum Difference = 18Explanation:Suppose arr[ ] = {5, 8, -1, 4}Let Subset A = {5, 8, 4} & Subset B = {-1}Sum of elements of subset A = 17, of subset B = -1Difference of Sum of Both subsets = 17 - (-1) = 18Input format :The first input line consists of the size of an array, n.The second input consists of the array elements, separated by space.Output format :The output displays the maximum possible difference between two subsets of an array.Refer to the sample output for the formatting specifications.Code constraints :2 ≤ n ≤ 100Sample test cases :Input 1 :74 2 -3 3 -2 -2 8Output 1 :Maximum Difference = 20Input 2 :45 8 -1 4Output 2 :Maximum Difference = 18
Solution
Here is a Python solution for the problem:
def max_diff_subsets(arr):
arr.sort(reverse=True)
subset1 = []
subset2 = []
for i in arr:
if i not in subset1:
subset1.append(i)
elif i not in subset2:
subset2.append(i)
return abs(sum(subset1) - sum(subset2))
n = int(input())
arr = list(map(int, input().split()))
print("Maximum Difference =", max_diff_subsets(arr))
This program works by first sorting the array in descending order. Then it iterates over the array, adding each element to the first subset if it's not already there, or to the second subset if it's not already there. Finally, it returns the absolute difference between the sums of the two subsets.
Similar Questions
Given an integer array arr, write a program to find the subarray which has the largest sum and return its sum. If the array is empty, return 0.Sample Input:9-2 -1 -3 4 -1 2 1 -5 4Sample Output: 6Explanation:The subarray is [4, -1, 2, 1] and the sum is 6
Given an array Arr of size N containing positive integers. Find the maximum sum of a any possible subsequence such that no two numbers in the subsequence should be adjacent in Arr.
Given an array of integers, find the longest subarray where the absolute difference between any two elements is less than or equal to .
Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray.Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a 32-bit integer. Example 1:Input: arr = [1,15,7,9,2,5,10], k = 3Output: 84Explanation: arr becomes [15,15,15,9,10,10,10]
Given an array of integers, find the longest subarray where the absolute difference between any two elements is less than or equal to .ExampleThere are two subarrays meeting the criterion: and . The maximum length subarray has elements.Function DescriptionComplete the pickingNumbers function in the editor below.pickingNumbers has the following parameter(s):int a[n]: an array of integersReturnsint: the length of the longest subarray that meets the criterionInput FormatThe first line contains a single integer , the size of the array .The second line contains space-separated integers, each an .ConstraintsThe answer will be .Sample Input 064 6 5 3 3 1Sample Output 03Explanation 0We choose the following multiset of integers from the array: . Each pair in the multiset has an absolute difference (i.e., and ), so we print the number of chosen integers, , as our answer.Sample Input 161 2 2 3 1 2Sample Output 15Explanation 1We choose the following multiset of integers from the array: . Each pair in the multiset has an absolute difference (i.e., , , and ), so we print the number of chosen integers, , as our answer.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.