Dada una array arr[] de N enteros positivos y un rango [L, R] , la tarea es encontrar la suma máxima del subconjunto tal que la diferencia entre los elementos máximo y mínimo del subconjunto se encuentre en el rango dado.
Ejemplos:
Entrada: arr[] = {6, 5, 0, 9, 1}, L = 0, R = 3
Salida: 15
Explicación: El subconjunto {6, 9} de la array dada tiene la diferencia entre los elementos máximo y mínimo como 3 que se encuentra en el rango dado [0, 3] y la suma de los elementos como 15 que es el máximo posible.Entrada: arr[] = {5, 10, 15, 20, 25}, L = 1, R = 2
Salida: 0
Explicación: No existen subconjuntos válidos.
Enfoque: el problema dado se puede resolver con la ayuda de una búsqueda binaria después de ordenar la array dada . A continuación se detallan los pasos a seguir:
- Ordena la array dada en orden no decreciente.
- Cree una array de suma de prefijos sum [] usando el algoritmo discutido aquí .
- Recorra la array usando una variable i para todos los valores de i en el rango [0, N) .
- Para cada i , encuentre el índice j del entero más grande tal que arr[j] <= arr[i] + R . Esto se puede hacer usando la función upper_bound .
- Mantenga una variable ans , que almacene la suma máxima del subconjunto. Inicialmente, respuesta = 0 .
- Si el subarreglo arr[i, j] forma un subconjunto válido, actualice el valor de ans al máximo de ans y la suma del subarreglo arr[i, j] .
- El valor almacenado en ans es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
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
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>
Producción:
15
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA