Dada una array de enteros no negativos y una suma. Tenemos que encontrar la suma del subarreglo que tiene una suma máxima menor o igual que la suma dada en el arreglo.
( Nota: la array dada contiene solo números enteros no negativos).
Ejemplos:
Input : arr[] = { 1, 2, 3, 4, 5 }
sum = 11
Output : 10
Subarray having maximum sum is { 1, 2, 3, 4 }
Input : arr[] = { 2, 4, 6, 8, 10 }
sum = 7
Output : 6
Subarray having maximum sum is { 2, 4 } or { 6 }
Enfoque ingenuo: podemos encontrar la suma máxima del subarreglo ejecutando dos bucles. Pero la complejidad del tiempo será O(N*N).
Enfoque eficiente: el subarreglo que tiene la suma máxima se puede encontrar usando una ventana deslizante . Si curr_sum es menor que sum, incluya elementos de array. Si se vuelve mayor que la suma, elimina los elementos desde el inicio en curr_sum. (Esto funcionará solo en el caso de elementos no negativos).
Implementación:
C++
// C++ program to find subarray having
// maximum sum less than or equal to sum
#include <bits/stdc++.h>
using namespace std;
// To find subarray with maximum sum
// less than or equal to sum
int findMaxSubarraySum(int arr[], int n, int sum)
{
// To store current sum and
// max sum of subarrays
int curr_sum = arr[0], max_sum = 0, start = 0;
// To find max_sum less than sum
for (int i = 1; i < n; i++) {
// Update max_sum if it becomes
// greater than curr_sum
if (curr_sum <= sum)
max_sum = max(max_sum, curr_sum);
// If curr_sum becomes greater than
// sum subtract starting elements of array
while (start < i && curr_sum + arr[i] > sum) {
curr_sum -= arr[start];
start++;
}
// If cur_sum becomes negative then start new subarray
if (curr_sum < 0)
{
curr_sum = 0;
}
// Add elements to curr_sum
curr_sum += arr[i];
}
// Adding an extra check for last subarray
if (curr_sum <= sum)
max_sum = max(max_sum, curr_sum);
return max_sum;
}
// Driver program to test above function
int main()
{
int arr[] = {6, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 20;
cout << findMaxSubarraySum(arr, n, sum);
return 0;
}
Java
// Java program to find subarray having
// maximum sum less than or equal to sum
public class Main {
// To find subarray with maximum sum
// less than or equal to sum
static int findMaxSubarraySum(int arr[],
int n, int sum)
{
// To store current sum and
// max sum of subarrays
int curr_sum = arr[0], max_sum = 0, start = 0;
// To find max_sum less than sum
for (int i = 1; i < n; i++) {
// Update max_sum if it becomes
// greater than curr_sum
if (curr_sum <= sum)
max_sum = Math.max(max_sum, curr_sum);
// If curr_sum becomes greater than
// sum subtract starting elements of array
while (curr_sum + arr[i] > sum && start < i) {
curr_sum -= arr[start];
start++;
}
// Add elements to curr_sum
curr_sum += arr[i];
}
// Adding an extra check for last subarray
if (curr_sum <= sum)
max_sum = Math.max(max_sum, curr_sum);
return max_sum;
}
// Driver program to test above function
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = arr.length;
int sum = 11;
System.out.println(findMaxSubarraySum(arr, n, sum));
}
}
Python3
# Python3 program to find subarray having # maximum sum less than or equal to sum # To find subarray with maximum sum # less than or equal to sum def findMaxSubarraySum(arr, n, sum): # To store current sum and # max sum of subarrays curr_sum = arr[0] max_sum = 0 start = 0; # To find max_sum less than sum for i in range(1, n): # Update max_sum if it becomes # greater than curr_sum if (curr_sum <= sum): max_sum = max(max_sum, curr_sum) # If curr_sum becomes greater than sum # subtract starting elements of array while (curr_sum + arr[i] > sum and start < i): curr_sum -= arr[start] start += 1 # Add elements to curr_sum curr_sum += arr[i] # Adding an extra check for last subarray if (curr_sum <= sum): max_sum = max(max_sum, curr_sum) return max_sum # Driver Code if __name__ == '__main__': arr = [6, 8, 9] n = len(arr) sum = 20 print(findMaxSubarraySum(arr, n, sum)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find subarray
// having maximum sum less
//than or equal to sum
using System;
public class GFG
{
// To find subarray with maximum
// sum less than or equal
// to sum
static int findMaxSubarraySum(int []arr,
int n, int sum)
{ // To store current sum and
// max sum of subarrays
int curr_sum = arr[0], max_sum = 0, start = 0;
// To find max_sum less than sum
for (int i = 1; i < n; i++) {
// Update max_sum if it becomes
// greater than curr_sum
if (curr_sum <= sum)
max_sum = Math.Max(max_sum, curr_sum);
// If curr_sum becomes greater than
// sum subtract starting elements of array
while (curr_sum + arr[i] > sum && start < i) {
curr_sum -= arr[start];
start++;
}
// Add elements to curr_sum
curr_sum += arr[i];
}
// Adding an extra check for last subarray
if (curr_sum <= sum)
max_sum = Math.Max(max_sum, curr_sum);
return max_sum;
}
// Driver Code
public static void Main()
{
int []arr = {1, 2, 3, 4, 5};
int n = arr.Length;
int sum = 11;
Console.Write(findMaxSubarraySum(arr, n, sum));
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to find subarray having
// maximum sum less than or equal to sum
// To find subarray with maximum sum
// less than or equal to sum
function findMaxSubarraySum(&$arr, $n, $sum)
{
// To store current sum and
// max sum of subarrays
$curr_sum = $arr[0];
$max_sum = 0;
$start = 0;
// To find max_sum less than sum
for ($i = 1; $i < $n; $i++)
{
// Update max_sum if it becomes
// greater than curr_sum
if ($curr_sum <= $sum)
$max_sum = max($max_sum, $curr_sum);
// If curr_sum becomes greater than
// sum subtract starting elements of array
while ($curr_sum + $arr[$i] > $sum &&
$start < $i)
{
$curr_sum -= $arr[$start];
$start++;
}
// Add elements to curr_sum
$curr_sum += $arr[$i];
}
// Adding an extra check for last subarray
if ($curr_sum <= $sum)
$max_sum = max($max_sum, $curr_sum);
return $max_sum;
}
// Driver Code
$arr = array(6, 8, 9);
$n = sizeof($arr);
$sum = 20;
echo findMaxSubarraySum($arr, $n, $sum);
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript program to find subarray having
// maximum sum less than or equal to sum
// To find subarray with maximum sum
// less than or equal to sum
function findMaxSubarraySum(arr, n, sum)
{
// To store current sum and
// max sum of subarrays
let curr_sum = arr[0], max_sum = 0,
start = 0;
// To find max_sum less than sum
for(let i = 1; i < n; i++)
{
// Update max_sum if it becomes
// greater than curr_sum
if (curr_sum <= sum)
max_sum = Math.max(max_sum, curr_sum);
// If curr_sum becomes greater than
// sum subtract starting elements of array
while (curr_sum + arr[i] > sum && start < i)
{
curr_sum -= arr[start];
start++;
}
// Add elements to curr_sum
curr_sum += arr[i];
}
// Adding an extra check for last subarray
if (curr_sum <= sum)
max_sum = Math.max(max_sum, curr_sum);
return max_sum;
}
// Driver code
let arr = [ 6, 8, 9 ];
let n = arr.length;
let sum = 20;
document.write(findMaxSubarraySum(arr, n, sum));
// This code is contributed by Mayank Tyagi
</script>
17
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)
Si se proporciona una array con todos los tipos (positivo, negativo o cero) de elementos, podemos usar la suma y los conjuntos de prefijos y la complejidad de tiempo en el peor de los casos será O (n.log (n)). Puede hacer referencia a la suma máxima de subarreglo menor o igual a k usando el artículo establecido para una mayor claridad de este método.
Este artículo es una contribución de nuclode . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA