Suma máxima de subarreglo en O (n) usando suma de prefijo

Posted on by Rudeus Greyrat

Dada una array de enteros positivos y negativos, encuentre la suma máxima de subarreglo en esa array.
 

Ejemplos: 
 

Input1 : arr = {-2, -3, 4, -1, -2, 1, 5, -3}
Output1 : 7

Input2 : arr = {4, -8, 9, -4, 1, -8, -1, 6}
Output2 : 9

El Algoritmo de Kadane resuelve este problema utilizando el enfoque de Programación Dinámica en tiempo lineal. Aquí hay otro enfoque que utiliza la programación dinámica y la suma de prefijos para encontrar la suma máxima de subarreglo en tiempo lineal.
Prerrequisito: array de suma de prefijos
 

1. Primero calcule la suma de prefijos (prefix_sum) de la array de entrada. 
2. La suma de un subarreglo del índice x al y se puede presentar como, 

$$\sum\limits_{ele=x}^{y} arr[ele] = prefix\_sum[y] - prefix\_sum[x-1] $$

3. Ahora el máximo de estos subarreglos es, 

$$max(\sum\limits_{ele=x}^{y} arr[ele]) = max(prefix\_sum[y] - prefix\_sum[x-1]) =$$$$max_{1<=y<=n}(prefix\_sum[y] - min_{x<=y}(prefix\_sum[x-1])) $$

Es decir, hacemos un seguimiento de la suma mínima de prefijos para x <= y y la suma máxima de subarreglo hasta el momento. 
 

Implementación: 
1. Calcule la suma del prefijo de la array de entrada. 
2. Inicialice: min_prefix_sum = 0, res = -infinite 
3. Mantenga un bucle para i = 0 a n. (n es el tamaño de la array de entrada). 
     a) cand = prefix_sum[i] – mini
     b) Si cand es mayor que res (la suma máxima del subarreglo hasta ahora), entonces actualice res por cand.
     c) Si prefix_sum[i] es menor que min_prefix_sum (la suma mínima de prefijos hasta ahora), actualice min_prefix_sum por prefix_sum[i].
4. Devolver res.
Referencia: Algoritmos para el problema de k sumas máximas y un algoritmo VLSI para el problema de k subarreglos máximos
 

C++

// C++ program to find out maximum subarray
// sum in linear time using prefix sum.
#include <iostream>
#include <limits>
using namespace std;
 
// Function to compute maximum subarray
// sum in linear time.
int maximumSumSubarray(int arr[], int n)
{
    // Initialize minimum prefix sum to 0.
    int min_prefix_sum = 0;
 
    // Initialize maximum subarray sum so
    // far to -infinity.
    int res = numeric_limits<int>::min();
 
    // Initialize and compute the prefix
    // sum array.
    int prefix_sum[n];
    prefix_sum[0] = arr[0];
    for (int i = 1; i < n; i++)
        prefix_sum[i] = prefix_sum[i - 1] + arr[i];       
 
    // loop through the array, keep track
    // of minimum prefix sum so far and
    // maximum subarray sum.
    for (int i = 0; i < n; i++) {
        res = max(res, prefix_sum[i] -
                       min_prefix_sum);
        min_prefix_sum = min(min_prefix_sum,
                             prefix_sum[i]);
    }
     
    return res;
}
 
// Driver Program
int main()
{
    // Test case 1
    int arr1[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    cout << maximumSumSubarray(arr1, n1) << endl;
 
    // Test case 2
    int arr2[] = { 4, -8, 9, -4, 1, -8, -1, 6 };
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    cout << maximumSumSubarray(arr2, n2);
 
    return 0;
}

Java

// Java program to find
// out maximum subarray
// sum in linear time
// using prefix sum.
 
class GFG
{
    // Function to compute maximum
    // subarray sum in linear time.
    static int maximumSumSubarray(int arr[], int n)
    {
        // Initialize minimum
        // prefix sum to 0.
        int min_prefix_sum = 0;
     
        // Initialize maximum subarray
        // sum so far to -infinity.
        int res = Integer.MIN_VALUE;
     
        // Initialize and compute
        // the prefix sum array.
        int prefix_sum[] = new int[n];
        prefix_sum[0] = arr[0];
        for (int i = 1; i < n; i++)
            prefix_sum[i] = prefix_sum[i - 1]
                            + arr[i];    
     
        // loop through the array, keep
        // track of minimum prefix sum so
        // far and maximum subarray sum.
        for (int i = 0; i < n; i++)
        {
            res = Math.max(res, prefix_sum[i] -
                           min_prefix_sum);
            min_prefix_sum = Math.min(min_prefix_sum,
                                     prefix_sum[i]);
        }
         
        return res;
    }
     
    // Driver Program
    public static void main (String[] args)
    {
        // Test case 1
        int arr1[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
        int n1 = arr1.length;
        System.out.println(maximumSumSubarray(arr1, n1));
     
        // Test case 2
        int arr2[] = { 4, -8, 9, -4, 1, -8, -1, 6 };
        int n2 = arr2.length;
        System.out.println(maximumSumSubarray(arr2, n2));
    }
}
 
// This code is contributed by Ansu Kumari.

Python3

# Python3 program to find out
# maximum subarray sum in
# linear time using prefix
# sum.
import math
 
# Function to compute maximum
# subarray sum in linear time.
def maximumSumSubarray(arr, n):
     
    # Initialize minimum prefix
    # sum to 0.
    min_prefix_sum = 0
 
    # Initialize maximum subarray
    # sum so far to -infinity.
    res = -math.inf
 
    # Initialize and compute the
    # prefix sum array.
    prefix_sum = []
    prefix_sum.append(arr[0])
     
    for i in range(1, n):
        prefix_sum.append(prefix_sum[i - 1] + arr[i])    
 
    # loop through the array keep
    # track of minimum prefix sum
    # so far and maximum subarray
    # sum.
    for i in range(n):
         
        res = max(res, prefix_sum[i] - min_prefix_sum)
        min_prefix_sum = min(min_prefix_sum, prefix_sum[i])
     
    return res
 
# Driver Program
 
# Test case 1
arr1 = [ -2, -3, 4, -1, -2, 1, 5, -3 ]
n1 = len(arr1)
print(maximumSumSubarray(arr1, n1))
 
# Test case 2
arr2 = [ 4, -8, 9, -4, 1, -8, -1, 6 ]
n2 = len(arr2)
print(maximumSumSubarray(arr2, n2))
 
# This code is contributed by Ansu Kuamri.

C#

// C# program to find
// out maximum subarray
// sum in linear time
// using prefix sum.
using System;
 
class GFG
{
    // Function to compute maximum
    // subarray sum in linear time.
    static int maximumSumSubarray(int []arr, int n)
    {
        // Initialize minimum
        // prefix sum to 0.
        int min_prefix_sum = 0;
     
        // Initialize maximum subarray
        // sum so far to -infinity.
        int res = int.MinValue;
     
        // Initialize and compute
        // the prefix sum array.
        int []prefix_sum = new int[n];
        prefix_sum[0] = arr[0];
        for (int i = 1; i < n; i++)
            prefix_sum[i] = prefix_sum[i - 1]
                            + arr[i];
     
        // loop through the array, keep
        // track of minimum prefix sum so
        // far and maximum subarray sum.
        for (int i = 0; i < n; i++)
        {
            res = Math.Max(res, prefix_sum[i] -
                        min_prefix_sum);
            min_prefix_sum = Math.Min(min_prefix_sum,
                                    prefix_sum[i]);
        }
         
        return res;
    }
     
    // Driver Program
    public static void Main ()
    {
        // Test case 1
        int []arr1 = { -2, -3, 4, -1, -2, 1, 5, -3 };
        int n1 = arr1.Length;
        Console.WriteLine(maximumSumSubarray(arr1, n1));
     
        // Test case 2
        int []arr2 = { 4, -8, 9, -4, 1, -8, -1, 6 };
        int n2 = arr2.Length;
        Console.WriteLine(maximumSumSubarray(arr2, n2));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to find out
// maximum subarray sum in
// linear time using prefix sum.
 
// Function to compute maximum
// subarray sum in linear time.
function maximumSumSubarray($arr, $n)
{
    // Initialize minimum
    // prefix sum to 0.
    $min_prefix_sum = 0;
 
    // Initialize maximum subarray
    // sum so far to -infinity.
    $res = PHP_INT_MIN;
 
    // Initialize and compute
    // the prefix sum array.
    $prefix_sum = array();
    $prefix_sum[0] = $arr[0];
    for ($i = 1; $i < $n; $i++)
        $prefix_sum[$i] = $prefix_sum[$i - 1] +
                                      $arr[$i];
 
    // loop through the array,
    // keep track of minimum
    // prefix sum so far and
    // maximum subarray sum.
    for ($i = 0; $i < $n; $i++)
    {
        $res = max($res, $prefix_sum[$i] -
                         $min_prefix_sum);
        $min_prefix_sum = min($min_prefix_sum,
                              $prefix_sum[$i]);
    }
     
    return $res;
}
 
// Driver Code
 
// Test case 1
$arr1 = array(-2, -3, 4, -1,
              -2, 1, 5, -3);
$n1 = count($arr1);
echo maximumSumSubarray($arr1, $n1), " \n" ;
 
// Test case 2
$arr2 = array(4, -8, 9, -4,
              1, -8, -1, 6);
               
$n2 = count($arr2);
echo maximumSumSubarray($arr2, $n2);
 
// This code is contributed by anuj_67.
?>

Javascript

<script>
 
// JavaScript program to find
// out maximum subarray
// sum in linear time
// using prefix sum.
 
// Function to compute maximum
// subarray sum in linear time.
    function maximumSumSubarray(arr, n)
    {
        // Initialize minimum
        // prefix sum to 0.
        let min_prefix_sum = 0;
       
        // Initialize maximum subarray
        // sum so far to -infinity.
        let res = Number.MIN_VALUE;
       
        // Initialize and compute
        // the prefix sum array.
        let prefix_sum = [];
        prefix_sum[0] = arr[0];
        for (let i = 1; i < n; i++)
            prefix_sum[i] = prefix_sum[i - 1]
                            + arr[i];    
       
        // loop through the array, keep
        // track of minimum prefix sum so
        // far and maximum subarray sum.
        for (let i = 0; i < n; i++)
        {
            res = Math.max(res, prefix_sum[i] -
                           min_prefix_sum);
            min_prefix_sum = Math.min(min_prefix_sum,
                                     prefix_sum[i]);
        }
           
        return res;
    }
 
// Driver code
 
        // Test case 1
        let arr1 = [ -2, -3, 4, -1, -2, 1, 5, -3 ];
        let n1 = arr1.length;
        document.write(maximumSumSubarray(arr1, n1) + "<br/>");
       
        // Test case 2
        let arr2 = [ 4, -8, 9, -4, 1, -8, -1, 6 ];
        let n2 = arr2.length;
        document.write(maximumSumSubarray(arr2, n2));
            
</script>

Producción : 

7
9

Solución más simple y eficiente 
Complejidad de tiempo: O(n). Se necesita un tiempo lineal para calcular la suma del prefijo y se necesita un tiempo constante en cada iteración del ciclo for. Por lo tanto, la complejidad general es O(n) .
Tenga en cuenta que el problema anterior se puede resolver en O (n) tiempo y O (1) espacio adicional usando el algoritmo de Kadane
 

Publicación traducida automáticamente

Artículo escrito por egoista 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 *