Maximum subset sum having difference between its maximum and minimum in range [L, R] - Coding

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 Code
int 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 approach
import 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 approach
from functools import cmp_to_key
 
def 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 low
 
def 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 targetRange
 
def 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 Code
arr = [6, 5, 0, 9, 1]
L = 0
R = 3
print(maxSubsetSum(arr, L, R))
 
# This code is contributed by shinjanpatra

C#

// C# program for the above approach
using 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:

Time Complexity: O(N*log N)
Auxiliary Space: O(N)

Reffered: https://www.geeksforgeeks.org

Arrays

Related
Java Program To Recursively Remove All Adjacent Duplicates
Python Program To Recursively Remove All Adjacent Duplicates
Javascript Program For Swapping Kth Node From Beginning With Kth Node From End In A Linked List
Python Program for Leaders in an array
Minimum jumps required to reach all array elements using largest element

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	7