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