Subarreglo de suma máxima que tiene una suma menor o igual a la suma dada usando Set

Dada una array arr[] de longitud N y un entero K , la tarea es encontrar el subarreglo de suma máxima con una suma menor que K .

Nota: si K es menor que el elemento mínimo, devuelve INT_MIN.

Ejemplos: 

Entrada: arr[] = {-1, 2, 2}, K = 4 
Salida:
Explicación: 
El subarreglo con suma máxima que es menor que 4 es {-1, 2, 2}. 
El subarreglo {2, 2} tiene suma máxima = 4, pero no es menor que 4. 

Entrada: arr[] = {5, -2, 6, 3, -5}, K =15 
Salida: 12 
Explicación: 
El subarreglo con suma máxima que es menor que 15 es {5, -2, 6, 3}. 

Enfoque eficiente: la suma del subarreglo [i, j] viene dada por la suma acumulativa hasta j: la suma acumulativa hasta i del arreglo. Ahora el problema se reduce a encontrar dos índices i y j, tales que i < j y cum[j] – cum[i] sean lo más cercano a K pero menor que él.
Para resolver esto, itere la array de izquierda a derecha. Ponga la suma acumulada de los valores i que ha encontrado hasta ahora en un conjunto. Cuando está procesando cum[j], lo que necesita recuperar del conjunto es el número más pequeño del conjunto que es mayor o igual que cum[j] – K. Esto se puede hacer en O (logN) usando upper_bound en el conjunto. 

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program to find maximum sum
// subarray less than K
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to maximum required sum < K
int maxSubarraySum(int arr[], int N, int K)
{
 
    // Hash to lookup for value (cum_sum - K)
    set<int> cum_set;
    cum_set.insert(0);
 
    int max_sum = INT_MIN, cSum = 0;
 
    for (int i = 0; i < N; i++) {
 
        // getting cumulative sum from [0 to i]
        cSum += arr[i];
 
        // lookup for upperbound
        // of (cSum-K) in hash
        set<int>::iterator sit
            = cum_set.lower_bound(cSum - K);
 
        // check if upper_bound
        // of (cSum-K) exists
        // then update max sum
        if (sit != cum_set.end())
 
            max_sum = max(max_sum, cSum - *sit);
 
        // insert cumulative value in hash
        cum_set.insert(cSum);
    }
 
    // return maximum sum
    // lesser than K
    return max_sum;
}
 
// Driver code
int main()
{
 
    // initialise the array
    int arr[] = { 5, -2, 6, 3, -5 };
 
    // initialise the value of K
    int K = 15;
 
    // size of array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << maxSubarraySum(arr, N, K);
 
    return 0;
}

Java

// Java program to find maximum sum
// subarray less than K
import java.util.*;
import java.io.*;
 
class GFG{
     
// Function to maximum required sum < K
static int maxSubarraySum(int arr[], int N,
                          int K)
{
     
    // Hash to lookup for value (cum_sum - K)
    Set<Integer> cum_set = new HashSet<>();
    cum_set.add(0);
  
    int max_sum =Integer.MIN_VALUE, cSum = 0;
  
    for(int i = 0; i < N; i++)
    {
         
        // Getting cumulative sum from [0 to i]
        cSum += arr[i];
  
        // Lookup for upperbound
        // of (cSum-K) in hash
        ArrayList<Integer> al = new ArrayList<>();
        Iterator<Integer> it = cum_set.iterator();
        int end = 0;
         
        while (it.hasNext())
        {
            end = it.next();
            al.add(end);
        }
         
        Collections.sort(al);
        int sit = lower_bound(al, cSum - K);
         
        // Check if upper_bound
        // of (cSum-K) exists
        // then update max sum
        if (sit != end)
            max_sum = Math.max(max_sum,
                               cSum - sit);
  
        // Insert cumulative value in hash
        cum_set.add(cSum);
    }
  
    // Return maximum sum
    // lesser than K
    return max_sum;
}
 
static int lower_bound(ArrayList<Integer> al,
                       int x)
{
     
    // x is the target value or key
    int l = -1, r = al.size();
    while (l + 1 < r)
    {
        int m = (l + r) >>> 1;
        if (al.get(m) >= x)
            r = m;
        else
            l = m;
    }
    return r;
}
 
// Driver code
public static void main(String args[])
{
  
    // Initialise the array
    int arr[] = { 5, -2, 6, 3, -5 };
  
    // Initialise the value of K
    int K = 15;
  
    // Size of array
    int N = arr.length;
  
    System.out.println(maxSubarraySum(arr, N, K));
}
}
 
// This code is contributed by jyoti369

Python3

# Python3 program to find maximum sum
# subarray less than K
import sys
import bisect
 
# Function to maximum required sum < K
 
 
def maxSubarraySum(arr, N, K):
    # Hash to lookup for value (cum_sum - K)
    cum_set = set()
    cum_set.add(0)
 
    max_sum = 12
    cSum = 0
 
    for i in range(N):
         
        # getting cumulative sum from [0 to i]
        cSum += arr[i]
 
        # check if upper_bound
        # of (cSum-K) exists
        # then update max sum
        x = bisect.bisect_left(arr, cSum - K, lo=0, hi=len(arr))
        if x:
            max_sum = max(max_sum,x )
 
        # insert cumulative value in hash
        cum_set.add(cSum)
 
    # return maximum sum
    # lesser than K
    return max_sum
 
 
# Driver code
if __name__ == '__main__':
    # initialise the array
    arr = [5, -2, 6, 3, -5]
 
    # initialise the value of K
    K = 15
 
    # size of array
    N = len(arr)
 
    print(maxSubarraySum(arr, N, K))
 
# This code is contributed by Surendra_Gangwar

C#

// Java program to find maximum sum
// subarray less than K
using System;
using System.Collections.Generic;
class GFG {
 
    // Function to maximum required sum < K
    static int maxSubarraySum(int[] arr, int N, int K)
    {
 
        // Hash to lookup for value (cum_sum - K)
        HashSet<int> cum_set = new HashSet<int>();
        cum_set.Add(0);
        int max_sum = Int32.MinValue, cSum = 0;
        for (int i = 0; i < N; i++) {
 
            // Getting cumulative sum from [0 to i]
            cSum += arr[i];
 
            // Lookup for upperbound
            // of (cSum-K) in hash
            List<int> al = new List<int>();
            int end = 0;
            foreach(int it in cum_set)
            {
                end = it;
                al.Add(it);
            }
 
            al.Sort();
            int sit = lower_bound(al, cSum - K);
 
            // Check if upper_bound
            // of (cSum-K) exists
            // then update max sum
            if (sit != end)
                max_sum = Math.Max(max_sum, cSum - al.ElementAt(sit));
 
            // Insert cumulative value in hash
            cum_set.Add(cSum);
        }
 
        // Return maximum sum
        // lesser than K
        return max_sum;
    }
    static int lower_bound(List<int> al, int x)
    {
 
        // x is the target value or key
        int l = -1, r = al.Count;
        while (l + 1 < r) {
            int m = (l + r) >> 1;
            if (al[m] >= x)
                r = m;
            else
                l = m;
        }
        return r;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
 
        // Initialise the array
        int[] arr = { 5, -2, 6, 3, -5 };
 
        // Initialise the value of K
        int K = 15;
 
        // Size of array
        int N = arr.Length;
        Console.Write(maxSubarraySum(arr, N, K));
    }
}
 
// This code is contributed by chitranayal.

Javascript

<script>
 
// JavaScript program to find maximum sum
// subarray less than K
 
 
    // Function to maximum required sum < K
    function maxSubarraySum(arr, N, K)
    {
 
        // Hash to lookup for value (cum_sum - K)
        let cum_set = new Set();
 
        cum_set.add(0);
 
        let max_sum = Number.MIN_SAFE_INTEGER;
        let cSum = 0;
 
        for(let i = 0; i < N; i++){
 
            // Getting cumulative sum from [0 to i]
            cSum += arr[i];
 
            // Lookup for upperbound
            // of (cSum-K) in hash
            let al = [];
            let end = 0;
            for(let it of cum_set)
            {
                end = it;
                al.push(it);
            }
 
            al.sort((a, b) => a - b);
            let sit = lower_bound(al, cSum - K);
 
            // Check if upper_bound
            // of (cSum-K) exists
            // then update max sum
            if (sit != end)
                max_sum = Math.max(max_sum, cSum - sit);
 
            // Insert cumulative value in hash
            cum_set.add(cSum);
        }
 
        // Return maximum sum
        // lesser than K
        return max_sum;
    }
     
    let lower_bound =
    (al, x) => al.filter((item) => item > x )[0]    
 
    // Driver code
 
 
        // Initialise the array
        let arr = [ 5, -2, 6, 3, -5 ];
 
        // Initialise the value of K
        let K = 15;
 
        // Size of array
        let N = arr.length;
        document.write(maxSubarraySum(arr, N, K));
 
// This code is contributed by _saurabh_jaiswal
 
</script>
Producción

12

Complejidad de tiempo: O(N*Log(N)), donde N representa el tamaño de la array dada.

Espacio auxiliar: O(N), donde N representa el tamaño de la array dada.

Artículo similar: subarreglo de suma máxima que tiene una suma menor o igual a la suma dada usando la ventana deslizante
 

Publicación traducida automáticamente

Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *