Рубрики

Самая большая сумма смежных Subarray

Напишите эффективную программу для поиска суммы смежных подмассивов в одномерном массиве чисел с наибольшей суммой.

Алгоритм Кадане:

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far

Объяснение:
Простая идея алгоритма Кадане состоит в том, чтобы искать все положительные непрерывные сегменты массива (для этого используется max_ending_here). И отслеживать максимальную сумму непрерывного сегмента среди всех положительных сегментов (для этого используется max_so_far). Каждый раз, когда мы получаем положительную сумму, сравниваем ее с max_so_far и обновляем max_so_far, если она больше, чем max_so_far

    Lets take the example:
    {-2, -3, 4, -1, -2, 1, 5, -3}

    max_so_far = max_ending_here = 0

    for i=0,  a[0] =  -2
    max_ending_here = max_ending_here + (-2)
    Set max_ending_here = 0 because max_ending_here < 0

    for i=1,  a[1] =  -3
    max_ending_here = max_ending_here + (-3)
    Set max_ending_here = 0 because max_ending_here < 0

    for i=2,  a[2] =  4
    max_ending_here = max_ending_here + (4)
    max_ending_here = 4
    max_so_far is updated to 4 because max_ending_here greater 
    than max_so_far which was 0 till now

    for i=3,  a[3] =  -1
    max_ending_here = max_ending_here + (-1)
    max_ending_here = 3

    for i=4,  a[4] =  -2
    max_ending_here = max_ending_here + (-2)
    max_ending_here = 1

    for i=5,  a[5] =  1
    max_ending_here = max_ending_here + (1)
    max_ending_here = 2

    for i=6,  a[6] =  5
    max_ending_here = max_ending_here + (5)
    max_ending_here = 7
    max_so_far is updated to 7 because max_ending_here is 
    greater than max_so_far

    for i=7,  a[7] =  -3
    max_ending_here = max_ending_here + (-3)
    max_ending_here = 4

Программа:

C ++

// C ++ программа для вывода наибольшей суммы непрерывных массивов
#include<iostream>
#include<climits>

using namespace std;

  

int maxSubArraySum(int a[], int size)

{

    int max_so_far = INT_MIN, max_ending_here = 0;

  

    for (int i = 0; i < size; i++)

    {

        max_ending_here = max_ending_here + a[i];

        if (max_so_far < max_ending_here)

            max_so_far = max_ending_here;

  

        if (max_ending_here < 0)

            max_ending_here = 0;

    }

    return max_so_far;

}

  
/ * Драйвер программы для проверки maxSubArraySum * /

int main()

{

    int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};

    int n = sizeof(a)/sizeof(a[0]);

    int max_sum = maxSubArraySum(a, n);

    cout << "Maximum contiguous sum is " << max_sum;

    return 0;

}

Джава

import java.io.*;

// Java-программа для вывода наибольшей суммы непрерывных массивов

import java.util.*;

  

class Kadane

{

    public static void main (String[] args)

    {

        int [] a = {-2, -3, 4, -1, -2, 1, 5, -3};

        System.out.println("Maximum contiguous sum is " +

                                       maxSubArraySum(a));

    }

  

    static int maxSubArraySum(int a[])

    {

        int size = a.length;

        int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;

  

        for (int i = 0; i < size; i++)

        {

            max_ending_here = max_ending_here + a[i];

            if (max_so_far < max_ending_here)

                max_so_far = max_ending_here;

            if (max_ending_here < 0)

                max_ending_here = 0;

        }

        return max_so_far;

    }

}

питон

# Программа Python для поиска максимально смежного подмассива

   
# Функция поиска максимального смежного подмассива

from sys import maxint

def maxSubArraySum(a,size):

       

    max_so_far = -maxint - 1

    max_ending_here = 0

       

    for i in range(0, size):

        max_ending_here = max_ending_here + a[i]

        if (max_so_far < max_ending_here):

            max_so_far = max_ending_here

  

        if max_ending_here < 0:

            max_ending_here = 0   

    return max_so_far

   
# Функция драйвера для проверки вышеуказанной функции

a = [-13, -3, -25, -20, -3, -16, -23, -12, -5, -22, -15, -4, -7]

print "Maximum contiguous sum is", maxSubArraySum(a,len(a))

   
# Этот код предоставлен _Devesh Agrawal_

C #

// C # программа для печати самой большой
// непрерывная сумма массива

using System;

  

class GFG

{

    static int maxSubArraySum(int []a)

    {

        int size = a.Length;

        int max_so_far = int.MinValue, 

            max_ending_here = 0;

  

        for (int i = 0; i < size; i++)

        {

            max_ending_here = max_ending_here + a[i];

              

            if (max_so_far < max_ending_here)

                max_so_far = max_ending_here;

              

            if (max_ending_here < 0)

                max_ending_here = 0;

        }

          

        return max_so_far;

    }

      

    // Код диска

    public static void Main ()

    {

        int [] a = {-2, -3, 4, -1, -2, 1, 5, -3};

        Console.Write("Maximum contiguous sum is " +

                                maxSubArraySum(a));

    }

  
}

  
// Этот код предоставлен Sam007_

PHP

<?php
// PHP программа для печати крупнейших
// непрерывная сумма массива

  

function maxSubArraySum($a, $size)

{

    $max_so_far = PHP_INT_MIN; 

    $max_ending_here = 0;

  

    for ($i = 0; $i < $size; $i++)

    {

        $max_ending_here = $max_ending_here + $a[$i];

        if ($max_so_far < $max_ending_here)

            $max_so_far = $max_ending_here;

  

        if ($max_ending_here < 0)

            $max_ending_here = 0;

    }

    return $max_so_far;

}

  
// Код драйвера

$a = array(-2, -3, 4, -1,

           -2, 1, 5, -3);

$n = count($a);

$max_sum = maxSubArraySum($a, $n);

echo "Maximum contiguous sum is "

                          $max_sum;

  
// Этот код предоставлен anuj_67.
?>


Выход:

Maximum contiguous sum is 7

Выше программа может быть оптимизирована дальше, если мы сравним max_so_far с max_ending_here, только если max_ending_here больше 0.

C ++

int maxSubArraySum(int a[], int size)

{

   int max_so_far = 0, max_ending_here = 0;

   for (int i = 0; i < size; i++)

   {

       max_ending_here = max_ending_here + a[i];

       if (max_ending_here < 0)

           max_ending_here = 0;

  

       / * Не сравнивать по всем элементам. Сравнить только

          когда max_ending_here> 0 * /

       else if (max_so_far < max_ending_here)

           max_so_far = max_ending_here;

   }

   return max_so_far;

}

Джава

static int maxSubArraySum(int a[],int size) 

      

    int max_so_far = 0, max_ending_here = 0

  

    for (int i = 0; i < size; i++) 

    

        max_ending_here = max_ending_here + a[i];

        if (max_ending_here < 0

            max_ending_here = 0

          

        / * Не сравнивать для всех

           элементы. Сравнить только

           когда max_ending_here> 0 * /

        else if (max_so_far < max_ending_here) 

            max_so_far = max_ending_here; 

          

    

    return max_so_far; 

  
// Этот код предоставлен ANKITRAI1

питон

def maxSubArraySum(a,size):

      

    max_so_far = 0

    max_ending_here = 0

      

    for i in range(0, size):

        max_ending_here = max_ending_here + a[i]

        if max_ending_here < 0:

            max_ending_here = 0

          

        # Не сравнивать по всем элементам. Сравнить только

        # когда max_ending_here> 0

        elif (max_so_far < max_ending_here):

            max_so_far = max_ending_here

              

    return max_so_far

C #

static int maxSubArraySum(int[] a,

                          int size) 

int max_so_far = 0, 

    max_ending_here = 0; 

  

for (int i = 0; i < size; i++) 

    max_ending_here = max_ending_here + a[i];

    if (max_ending_here < 0) 

        max_ending_here = 0; 

      

    / * Не сравнивать для всех

    элементы. Сравнить только

    когда max_ending_here> 0 * /

    else if (max_so_far < max_ending_here) 

        max_so_far = max_ending_here; 

return max_so_far; 

  
// Этот код добавлен
// ChitraNayal

PHP

<?php 

function maxSubArraySum(&$a, $size)

{

$max_so_far = 0;

$max_ending_here = 0;

for ($i = 0; $i < $size; $i++)

{

    $max_ending_here = $max_ending_here + $a[$i];

    if ($max_ending_here < 0)

        $max_ending_here = 0;

  

    / * Не сравнивать по всем элементам.

       Сравнить только когда max_ending_here> 0 * /

    else if ($max_so_far < $max_ending_here)

        $max_so_far = $max_ending_here;

}

return $max_so_far;

  
// Этот код добавлен
// ChitraNayal
?>

Сложность времени: O (n)
Алгоритмическая парадигма: динамическое программирование

Ниже приводится еще одна простая реализация, предложенная Мохитом Кумаром . Реализация обрабатывает случай, когда все числа в массиве являются отрицательными.

C ++

#include<iostream>

using namespace std;

  

int maxSubArraySum(int a[], int size)

{

   int max_so_far = a[0];

   int curr_max = a[0];

  

   for (int i = 1; i < size; i++)

   {

        curr_max = max(a[i], curr_max+a[i]);

        max_so_far = max(max_so_far, curr_max);

   }

   return max_so_far;

}

  
/ * Драйвер программы для проверки maxSubArraySum * /

int main()

{

   int a[] =  {-2, -3, 4, -1, -2, 1, 5, -3};

   int n = sizeof(a)/sizeof(a[0]);

   int max_sum = maxSubArraySum(a, n);

   cout << "Maximum contiguous sum is " << max_sum;

   return 0;

}

Джава

// Java-программа для печати наибольшего смежного
// сумма массива

import java.io.*;

  

class GFG {

  

    static int maxSubArraySum(int a[], int size)

    {

    int max_so_far = a[0];

    int curr_max = a[0];

  

    for (int i = 1; i < size; i++)

    {

           curr_max = Math.max(a[i], curr_max+a[i]);

        max_so_far = Math.max(max_so_far, curr_max);

    }

    return max_so_far;

    }

  

    / * Драйвер программы для проверки maxSubArraySum * /

    public static void main(String[] args)

    {

    int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};

    int n = a.length;   

    int max_sum = maxSubArraySum(a, n);

    System.out.println("Maximum contiguous sum is " 

                       + max_sum);

    }

}

  
// Этот код предоставлен Prerna Saini

питон

# Программа Python для поиска максимально смежного подмассива

  

def maxSubArraySum(a,size):

      

    max_so_far =a[0]

    curr_max = a[0]

      

    for i in range(1,size):

        curr_max = max(a[i], curr_max + a[i])

        max_so_far = max(max_so_far,curr_max)

          

    return max_so_far

  
# Функция драйвера для проверки вышеуказанной функции

a = [-2, -3, 4, -1, -2, 1, 5, -3]

print"Maximum contiguous sum is" , maxSubArraySum(a,len(a))

  
# Этот код предоставлен _Devesh Agrawal_

C #

// C # программа для печати самой большой
// непрерывная сумма массива

using System;

  

class GFG

{

    static int maxSubArraySum(int []a, int size)

    {

    int max_so_far = a[0];

    int curr_max = a[0];

  

    for (int i = 1; i < size; i++)

    {

        curr_max = Math.Max(a[i], curr_max+a[i]);

        max_so_far = Math.Max(max_so_far, curr_max);

    }

  

    return max_so_far;

    }

  

    // Код диска

    public static void Main ()

    {

        int []a = {-2, -3, 4, -1, -2, 1, 5, -3};

        int n = a.Length; 

        Console.Write("Maximum contiguous sum is "

                           + maxSubArraySum(a, n));

    }

  
}

  
// Этот код предоставлен Sam007_

PHP

<?php

function maxSubArraySum($a, $size)

{

    $max_so_far = $a[0];

    $curr_max = $a[0];

      

    for ($i = 1; $i < $size; $i++)

    {

        $curr_max = max($a[$i], 

                        $curr_max + $a[$i]);

        $max_so_far = max($max_so_far

                          $curr_max);

    }

    return $max_so_far;

}

  
// Код драйвера

$a = array(-2, -3, 4, -1, 

           -2, 1, 5, -3);

$n = sizeof($a);

$max_sum = maxSubArraySum($a, $n);

echo "Maximum contiguous sum is " .

                          $max_sum;

  
// Этот код добавлен
// Аканкша Рай (Abby_akku)
?>


Выход:

Maximum contiguous sum is 7

Чтобы напечатать подмассив с максимальной суммой, мы поддерживаем индексы всякий раз, когда получаем максимальную сумму.

C ++

// C ++ программа для вывода наибольшей суммы непрерывных массивов
#include<iostream>
#include<climits>

using namespace std;

  

int maxSubArraySum(int a[], int size)

{

    int max_so_far = INT_MIN, max_ending_here = 0,

       start =0, end = 0, s=0;

  

    for (int i=0; i< size; i++ )

    {

        max_ending_here += a[i];

  

        if (max_so_far < max_ending_here)

        {

            max_so_far = max_ending_here;

            start = s;

            end = i;

        }

  

        if (max_ending_here < 0)

        {

            max_ending_here = 0;

            s = i + 1;

        }

    }

    cout << "Maximum contiguous sum is "

        << max_so_far << endl;

    cout << "Starting index "<< start

        << endl << "Ending index "<< end << endl;

}

  
/ * Драйвер программы для проверки maxSubArraySum * /

int main()

{

    int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};

    int n = sizeof(a)/sizeof(a[0]);

    int max_sum = maxSubArraySum(a, n);

    return 0;

}

Джава

// Java-программа для печати крупнейших
// непрерывная сумма массива

class GFG {

  

    static void maxSubArraySum(int a[], int size)

    {

        int max_so_far = Integer.MIN_VALUE,

        max_ending_here = 0,start = 0,

        end = 0, s = 0;

  

        for (int i = 0; i < size; i++) 

        {

            max_ending_here += a[i];

  

            if (max_so_far < max_ending_here) 

            {

                max_so_far = max_ending_here;

                start = s;

                end = i;

            }

  

            if (max_ending_here < 0

            {

                max_ending_here = 0;

                s = i + 1;

            }

        }

        System.out.println("Maximum contiguous sum is " 

                           + max_so_far);

        System.out.println("Starting index " + start);

        System.out.println("Ending index " + end);

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 };

        int n = a.length;

        maxSubArraySum(a, n);

    }

}

  
// Этот код предоставлен prerna saini

python3

# Программа Python для вывода наибольшей суммы непрерывных массивов

  

from sys import maxsize

  
# Функция поиска максимального смежного подмассива
# и распечатать его начальный и конечный индексы

def maxSubArraySum(a,size):

  

    max_so_far = -maxsize - 1

    max_ending_here = 0

    start = 0

    end = 0

    s = 0

  

    for i in range(0,size):

  

        max_ending_here += a[i]

  

        if max_so_far < max_ending_here:

            max_so_far = max_ending_here

            start = s

            end = i

  

        if max_ending_here < 0:

            max_ending_here = 0

            s = i+1

  

    print ("Maximum contiguous sum is %d"%(max_so_far))

    print ("Starting Index %d"%(start))

    print ("Ending Index %d"%(end))

  
# Драйвер программы для проверки maxSubArraySum

a = [-2, -3, 4, -1, -2, 1, 5, -3]

maxSubArraySum(a,len(a))

C #

// C # программа для печати самой большой
// непрерывная сумма массива

using System;

  

class GFG 

{

    static void maxSubArraySum(int []a, 

                               int size)

    {

        int max_so_far = int.MinValue,

        max_ending_here = 0, start = 0,

        end = 0, s = 0;

  

        for (int i = 0; i < size; i++) 

        {

            max_ending_here += a[i];

  

            if (max_so_far < max_ending_here) 

            {

                max_so_far = max_ending_here;

                start = s;

                end = i;

            }

  

            if (max_ending_here < 0) 

            {

                max_ending_here = 0;

                s = i + 1;

            }

        }

        Console.WriteLine("Maximum contiguous "

                         "sum is " + max_so_far);

        Console.WriteLine("Starting index "

                                      start);

        Console.WriteLine("Ending index "

                                      end);

    }

  

    // Код драйвера

    public static void Main()

    {

        int []a = {-2, -3, 4, -1, 

                   -2, 1, 5, -3};

        int n = a.Length;

        maxSubArraySum(a, n);

    }

}

  
// Этот код добавлен
// от anuj_67.

PHP

<?php 
// PHP программа для печати крупнейших
// непрерывная сумма массива

  

function maxSubArraySum($a, $size)

{

    $max_so_far = PHP_INT_MIN;

    $max_ending_here = 0;

    $start = 0;

    $end = 0;

    $s = 0;

  

    for ($i = 0; $i < $size; $i++)

    {

        $max_ending_here += $a[$i];

  

        if ($max_so_far < $max_ending_here)

        {

            $max_so_far = $max_ending_here;

            $start = $s;

            $end = $i;

        }

  

        if ($max_ending_here < 0)

        {

            $max_ending_here = 0;

            $s = $i + 1;

        }

    }

    echo "Maximum contiguous sum is ".

                     $max_so_far."\n";

    echo "Starting index ". $start . "\n".

            "Ending index " . $end . "\n";

}

  
// Код драйвера

$a = array(-2, -3, 4, -1, -2, 1, 5, -3);

$n = sizeof($a);

$max_sum = maxSubArraySum($a, $n);

  
// Этот код добавлен
// ChitraNayal
?>


Выход:

Maximum contiguous sum is 7
Starting index 2
Ending index 6

Теперь попробуйте ниже вопрос
Учитывая массив целых чисел (возможно, некоторые из отрицательных элементов), напишите программу на C, чтобы выяснить * максимальный возможный продукт * путем умножения 'n' последовательных целых чисел в массиве, где n <= ARRAY_SIZE. Также напечатайте начальную точку максимального массива продукта.

Ссылки:
http://en.wikipedia.org/wiki/Kadane%27s_Algorithm

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Самая большая сумма смежных Subarray

0.00 (0%) 0 votes