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: 3
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>
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