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

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>
Producción: 

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

Deja una respuesta

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