Given an array arr[] of N positive integers and a range [L, R], the task is to find the maximum subset-sum such that the difference between the maximum and minimum elements of the subset lies in the given range.
Examples:
Input: arr[] = {6, 5, 0, 9, 1}, L = 0, R = 3
Output: 15
Explanation: The subset {6, 9} of the given array has the difference between maximum and minimum elements as 3 which lies in the given range [0, 3] and the sum of the elements as 15 which is the maximum possible.Input: arr[] = {5, 10, 15, 20, 25}, L = 1, R = 2
Output: 0
Explanation: There exist no valid subsets.
Approach: The given problem can be solved with the help of a Binary Search after sorting the given array. Below are the steps to follow:
- Sort the given array in non-decreasing order.
- Create a prefix sum array sum[] using the algorithm discussed here.
- Traverse the array using a variable i for all values of i in the range [0, N).
- For each i, find the index j of the largest integer such that arr[j] <= arr[i] + R. This can be done using the upper_bound function.
- Maintain a variable ans, which stores the maximum subset-sum. Initially, ans = 0.
- If the subarray arr[i, j] forms a valid subset, update the value of ans to the max of ans and sum of the subarray arr[i, j].
- The value stored in ans is the required answer.
Below is the implementation of the above approach:
CPP
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find Maximum Subset Sum such// that the difference between maximum and// minimum elements lies in the range [L, R]int maxSubsetSum(vector<int> arr, int L, int R){ int N = arr.size(); // Sort the given array arr[] in // non-decreasing order sort(arr.begin(), arr.end()); // Stores the sum of elements till // current index of the array arr[] int sum[N + 1] = {}; // Stores the Maximum subset sum int ans = 0; // Create prefix sum array for (int i = 1; i <= N; i++) { sum[i] = sum[i - 1] + arr[i - 1]; } // Iterate over all indices of array for (int i = 0; i < N; i++) { // Maximum possible value of // subset considering arr[i] // as the minimum element int val = arr[i] + R; // Calculate the position of the // largest element <= val auto ptr = upper_bound( arr.begin(), arr.end(), val); ptr--; int j = ptr - arr.begin(); // If the difference between the // maximum and the minimum lies in // the range, update answer if ((arr[j] - arr[i] <= R) && (arr[j] - arr[i] >= L)) { ans = max(ans, sum[j + 1] - sum[i]); } } // Return Answer return ans;}// Driver Codeint main(){ vector<int> arr{ 6, 5, 0, 9, 1 }; int L = 0; int R = 3; cout << maxSubsetSum(arr, L, R); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static int upperBound(int[] a, int low, int high, int element){ while(low < high){ int middle = low + (high - low)/2; if(a[middle] > element) high = middle; else low = middle + 1; } return low; } // Function to find Maximum Subset Sum such // that the difference between maximum and // minimum elements lies in the range [L, R] static int maxSubsetSum(int[] arr, int L, int R) { int N = arr.length; // Sort the given array arr[] in // non-decreasing order Arrays.sort(arr); // Stores the sum of elements till // current index of the array arr[] int []sum = new int[N + 1]; // Stores the Maximum subset sum int ans = 0; // Create prefix sum array for (int i = 1; i <= N; i++) { sum[i] = sum[i - 1] + arr[i - 1]; } // Iterate over all indices of array for (int i = 0; i < N; i++) { // Maximum possible value of // subset considering arr[i] // as the minimum element int val = arr[i] + R; // Calculate the position of the // largest element <= val int ptr = upperBound(arr, 0, N,val); ptr--; int j = ptr; // If the difference between the // maximum and the minimum lies in // the range, update answer if ((arr[j] - arr[i] <= R) && (arr[j] - arr[i] >= L)) { ans = Math.max(ans, sum[j + 1] - sum[i]); } } // Return Answer return ans; } // Driver Code public static void main(String[] args) { int[] arr = { 6, 5, 0, 9, 1 }; int L = 0; int R = 3; System.out.print(maxSubsetSum(arr, L, R)); }}// This code is contributed by umadevi9616 |
Python3
# Python Program to implement# the above approachfrom functools import cmp_to_keydef cmp_sort(a, b): return a - b def InsertionIndex(nums, target, left): low = 0 high = len(nums) while (low < high): mid = low + ((high - low) // 2) if (nums[mid] > target or (left and target == nums[mid])): high = mid else: low = mid + 1 return lowdef upper_bound(nums, target): targetRange = [-1, -1] leftIdx = InsertionIndex(nums, target, True) if (leftIdx == len(nums) or nums[leftIdx] != target): return targetRange targetRange[0] = leftIdx targetRange[1] = InsertionIndex(nums, target, False) - 1 return targetRangedef maxSubsetSum(arr, L, R): N = len(arr) # Sort the given array arr[] in # non-decreasing order arr.sort(key = cmp_to_key(cmp_sort)) # Stores the sum of elements till # current index of the array arr[] sum = [0 for i in range(N+1)] # Stores the Maximum subset sum ans = 0 # Create prefix sum array for i in range(1,N+1): sum[i] = sum[i - 1] + arr[i - 1] # Iterate over all indices of array for i in range(N): # Maximum possible value of # subset considering arr[i] # as the minimum element val = arr[i] + R # Calculate the position of the # largest element <= val ptr = upper_bound(arr, val) j = ptr[1] # If the difference between the # maximum and the minimum lies in # the range, update answer if ((arr[j] - arr[i] <= R) and (arr[j] - arr[i] >= L)): ans = max(ans, sum[j + 1] - sum[i]) # Return Answer return ans# Driver Codearr = [6, 5, 0, 9, 1]L = 0R = 3print(maxSubsetSum(arr, L, R))# This code is contributed by shinjanpatra |
C#
// C# program for the above approachusing System;class GFG { static int upperBound(int[] a, int low, int high, int element) { while (low < high) { int middle = low + (high - low) / 2; if (a[middle] > element) high = middle; else low = middle + 1; } return low; } // Function to find Maximum Subset Sum such // that the difference between maximum and // minimum elements lies in the range [L, R] static int maxSubsetSum(int[] arr, int L, int R) { int N = arr.Length; // Sort the given array arr[] in // non-decreasing order Array.Sort(arr); // Stores the sum of elements till // current index of the array arr[] int[] sum = new int[N + 1]; // Stores the Maximum subset sum int ans = 0; // Create prefix sum array for (int i = 1; i <= N; i++) { sum[i] = sum[i - 1] + arr[i - 1]; } // Iterate over all indices of array for (int i = 0; i < N; i++) { // Maximum possible value of // subset considering arr[i] // as the minimum element int val = arr[i] + R; // Calculate the position of the // largest element <= val int ptr = upperBound(arr, 0, N, val); ptr--; int j = ptr; // If the difference between the // maximum and the minimum lies in // the range, update answer if ((arr[j] - arr[i] <= R) && (arr[j] - arr[i] >= L)) { ans = Math.Max(ans, sum[j + 1] - sum[i]); } } // Return Answer return ans; } // Driver Code static void Main(string[] args) { int[] arr = { 6, 5, 0, 9, 1 }; int L = 0; int R = 3; Console.WriteLine(maxSubsetSum(arr, L, R)); }}// This code is contributed by phasing17 |
Javascript
<script> // JavaScript Program to implement // the above approach function InsertionIndex(nums, target, left) { let low = 0, high = nums.length while (low < high) { const mid = low + Math.floor((high - low) / 2) if (nums[mid] > target || (left && target === nums[mid])) high = mid else low = mid + 1 } return low } function upper_bound(nums, target) { const targetRange = [-1, -1] const leftIdx = InsertionIndex(nums, target, true) if (leftIdx === nums.length || nums[leftIdx] != target) return targetRange targetRange[0] = leftIdx targetRange[1] = InsertionIndex(nums, target, false) - 1 return targetRange } function maxSubsetSum(arr, L, R) { let N = arr.length; // Sort the given array arr[] in // non-decreasing order arr.sort(function (a, b) { return a - b }) // Stores the sum of elements till // current index of the array arr[] let sum = new Array(N + 1).fill(0); // Stores the Maximum subset sum let ans = 0; // Create prefix sum array for (let i = 1; i <= N; i++) { sum[i] = sum[i - 1] + arr[i - 1]; } // Iterate over all indices of array for (let i = 0; i < N; i++) { // Maximum possible value of // subset considering arr[i] // as the minimum element let val = arr[i] + R; // Calculate the position of the // largest element <= val let ptr = upper_bound( arr, val); let j = ptr[1] // If the difference between the // maximum and the minimum lies in // the range, update answer if ((arr[j] - arr[i] <= R) && (arr[j] - arr[i] >= L)) { ans = Math.max(ans, sum[j + 1] - sum[i]); } } // Return Answer return ans; } // Driver Code let arr = [6, 5, 0, 9, 1]; let L = 0; let R = 3; document.write(maxSubsetSum(arr, L, R)); // This code is contributed by Potta Lokesh </script> |
Output:
15
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
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!
