Subarreglo contiguo de suma más pequeña

Dada una array que contiene n enteros. El problema es encontrar la suma de los elementos del subarreglo contiguo que tiene la suma más pequeña (mínima).

Ejemplos: 

Input : arr[] = {3, -4, 2, -3, -1, 7, -5}
Output : -6
Subarray is {-4, 2, -3, -1} = -6

Input : arr = {2, 6, 8, 1, 4}
Output : 1

Enfoque ingenuo: Considere todos los subarreglos contiguos de diferentes tamaños y encuentre su suma. El subarreglo que tiene la suma más pequeña (mínima) es la respuesta requerida.

Enfoque eficiente: es una variación del problema de encontrar el subarreglo contiguo de suma más grande basado en la idea del algoritmo de Kadane. 

Algoritmo: 

smallestSumSubarr(arr, n)
    Initialize min_ending_here = INT_MAX
    Initialize min_so_far = INT_MAX
    
    for i = 0 to n-1
        if min_ending_here > 0
            min_ending_here = arr[i]        
        else
            min_ending_here += arr[i]
        min_so_far = min(min_so_far, min_ending_here)

    return min_so_far

Implementación:

// C++ implementation to find the smallest sum
// contiguous subarray
#include <bits/stdc++.h>
 
using namespace std;
 
// function to find the smallest sum contiguous subarray
int smallestSumSubarr(int arr[], int n)
{
    // to store the minimum value that is ending
    // up to the current index
    int min_ending_here = INT_MAX;
     
    // to store the minimum value encountered so far
    int min_so_far = INT_MAX;
     
    // traverse the array elements
    for (int i=0; i<n; i++)
    {
        // if min_ending_here > 0, then it could not possibly
        // contribute to the minimum sum further
        if (min_ending_here > 0)
            min_ending_here = arr[i];
         
        // else add the value arr[i] to min_ending_here   
        else
            min_ending_here += arr[i];
         
        // update min_so_far
        min_so_far = min(min_so_far, min_ending_here);           
    }
     
    // required smallest sum contiguous subarray value
    return min_so_far;
}
 
 
// Driver program to test above
int main()
{
    int arr[] = {3, -4, 2, -3, -1, 7, -5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Smallest sum: "
         << smallestSumSubarr(arr, n);
    return 0;    
}

// Java implementation to find the smallest sum
// contiguous subarray
class GFG {
     
    // function to find the smallest sum contiguous
    // subarray
    static int smallestSumSubarr(int arr[], int n)
    {
         
        // to store the minimum value that is
        // ending up to the current index
        int min_ending_here = 2147483647;
         
        // to store the minimum value encountered
        // so far
        int min_so_far = 2147483647;
         
        // traverse the array elements
        for (int i = 0; i < n; i++)
        {
             
            // if min_ending_here > 0, then it could
            // not possibly contribute to the
            // minimum sum further
            if (min_ending_here > 0)
                min_ending_here = arr[i];
             
            // else add the value arr[i] to
            // min_ending_here
            else
                min_ending_here += arr[i];
             
            // update min_so_far
            min_so_far = Math.min(min_so_far,
                                   min_ending_here);        
        }
         
        // required smallest sum contiguous
        // subarray value
        return min_so_far;
    }
     
    // Driver method
    public static void main(String[] args)
    {
         
        int arr[] = {3, -4, 2, -3, -1, 7, -5};
        int n = arr.length;
         
        System.out.print("Smallest sum: "
                + smallestSumSubarr(arr, n));
    }
}
 
// This code is contributed by Anant Agarwal.

# Python program to find the smallest sum
# contiguous subarray
maxsize=int(1e9+7)
 
# function to find the smallest sum
# contiguous subarray
def smallestSumSubarr(arr, n):
    # to store the minimum value that is ending
    # up to the current index
    min_ending_here = maxsize
     
    # to store the minimum value encountered so far
    min_so_far = maxsize
     
    # traverse the array elements
    for i in range(n):
        # if min_ending_here > 0, then it could not possibly
        # contribute to the minimum sum further
        if (min_ending_here > 0):
            min_ending_here = arr[i]
         
        # else add the value arr[i] to min_ending_here
        else:
            min_ending_here += arr[i]
          
        # update min_so_far
        min_so_far = min(min_so_far, min_ending_here)
     
    # required smallest sum contiguous subarray value
    return min_so_far
     
# Driver code
arr = [3, -4, 2, -3, -1, 7, -5]
n = len(arr)
print ("Smallest sum: ", smallestSumSubarr(arr, n))
 
# This code is contributed by Sachin Bisht

// C# implementation to find the
// smallest sum contiguous subarray
using System;
 
class GFG {
 
    // function to find the smallest sum
    // contiguous subarray
    static int smallestSumSubarr(int[] arr, int n)
    {
        // to store the minimum value that is
        // ending up to the current index
        int min_ending_here = 2147483647;
 
        // to store the minimum value encountered
        // so far
        int min_so_far = 2147483647;
 
        // traverse the array elements
        for (int i = 0; i < n; i++) {
 
            // if min_ending_here > 0, then it could
            // not possibly contribute to the
            // minimum sum further
            if (min_ending_here > 0)
                min_ending_here = arr[i];
 
            // else add the value arr[i] to
            // min_ending_here
            else
                min_ending_here += arr[i];
 
            // update min_so_far
            min_so_far = Math.Min(min_so_far,
                                min_ending_here);
        }
 
        // required smallest sum contiguous
        // subarray value
        return min_so_far;
    }
 
    // Driver method
    public static void Main()
    {
 
        int[] arr = { 3, -4, 2, -3, -1, 7, -5 };
        int n = arr.Length;
 
        Console.Write("Smallest sum: " +
             smallestSumSubarr(arr, n));
    }
}
 
// This code is contributed by Sam007

<?php
// PHP implementation to find the
// smallest sum contiguous subarray
 
// function to find the smallest
// sum contiguous subarray
function smallestSumSubarr($arr, $n)
{
     
    // to store the minimum
    // value that is ending
    // up to the current index
    $min_ending_here = 999999;
     
    // to store the minimum value
    // encountered so far
    $min_so_far = 999999;
     
    // traverse the array elements
    for($i = 0; $i < $n; $i++)
    {
         
        // if min_ending_here > 0,
        // then it could not possibly
        // contribute to the minimum
        // sum further
        if ($min_ending_here > 0)
            $min_ending_here = $arr[$i];
         
        // else add the value arr[i]
        // to min_ending_here
        else
            $min_ending_here += $arr[$i];
         
        // update min_so_far
        $min_so_far = min($min_so_far,
                     $min_ending_here);        
    }
     
    // required smallest sum
    // contiguous subarray value
    return $min_so_far;
}
 
 
    // Driver Code
    $arr = array(3, -4, 2, -3, -1, 7, -5);
    $n = count($arr) ;
    echo "Smallest sum: "
         .smallestSumSubarr($arr, $n);
 
// This code is contributed by Sam007
?>

<script>
 
    // JavaScript implementation to find the
    // smallest sum contiguous subarray
     
    // function to find the smallest sum
    // contiguous subarray
    function smallestSumSubarr(arr, n)
    {
        // to store the minimum value that is
        // ending up to the current index
        let min_ending_here = 2147483647;
   
        // to store the minimum value encountered
        // so far
        let min_so_far = 2147483647;
   
        // traverse the array elements
        for (let i = 0; i < n; i++) {
   
            // if min_ending_here > 0, then it could
            // not possibly contribute to the
            // minimum sum further
            if (min_ending_here > 0)
                min_ending_here = arr[i];
   
            // else add the value arr[i] to
            // min_ending_here
            else
                min_ending_here += arr[i];
   
            // update min_so_far
            min_so_far = Math.min(min_so_far,
                                min_ending_here);
        }
   
        // required smallest sum contiguous
        // subarray value
        return min_so_far;
    }
     
    let arr = [ 3, -4, 2, -3, -1, 7, -5 ];
    let n = arr.length;
 
    document.write("Smallest sum: " +
                  smallestSumSubarr(arr, n));
     
</script>

Smallest sum: -6

Complejidad de tiempo: O(n)

Este artículo es una contribución de Ayush Jauhari . 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.