Рубрики

Максимальная круговая сумма подмассива

Учитывая n чисел (и + ve и -ve), расположенных по кругу, найти максимальную сумму последовательных чисел.

Примеры:

Input: a[] = {8, -8, 9, -9, 10, -11, 12}
Output: 22 (12 + 8 - 8 + 9 - 9 + 10)

Input: a[] = {10, -3, -4, 7, 6, 5, -4, -1} 
Output:  23 (7 + 6 + 5 - 4 -1 + 10) 

Input: a[] = {-1, 40, -14, 7, 6, 5, -4, -1}
Output: 52 (7 + 6 + 5 - 4 - 1 - 1 + 40)

На максимальную сумму может быть два случая:

Случай 1: элементы, которые вносят вклад в максимальную сумму, расположены так, что обертки нет. Примеры: {-10, 2, -1, 5}, {-2, 4, -1, 4, -1}. В этом случае алгоритм Кадане даст результат.

Случай 2: элементы, которые вносят вклад в максимальную сумму, расположены таким образом, что есть обертывание. Примеры: {10, -12, 11}, {12, -5, 4, -8, 11}. В этом случае мы изменяем упаковку на не-упаковку. Давайте посмотрим, как. Обтекание вспомогательных элементов подразумевает не оборачивание не вносящих вклад элементов, поэтому найдите сумму не вносящих вклад элементов и вычтите эту сумму из общей суммы. Чтобы узнать сумму не вносящих вклад, инвертируйте знак каждого элемента, а затем запустите алгоритм Кадане.
Наш массив подобен кольцу, и мы должны исключить максимальное непрерывное отрицание, которое подразумевает максимальное непрерывное отрицание в инвертированных массивах.

Наконец, мы сравниваем сумму, полученную в обоих случаях, и возвращаем максимум двух сумм.

Спасибо ashishdey0 за предложение этого решения. Ниже приведены реализации C / C ++, Java и Python вышеупомянутого метода.

C ++

// C ++ программа для задачи о максимальной непрерывной круговой сумме
#include <bits/stdc++.h>

using namespace std;

  
// Стандартный алгоритм Кадане для
// найти максимальную сумму подмассива

int kadane(int a[], int n); 

  
// Функция возвращает максимум
// круговая непрерывная сумма в []

int maxCircularSum(int a[], int n) 

    // Случай 1: получить максимальную сумму с использованием стандартного kadane '

    // алгоритм

    int max_kadane = kadane(a, n); 

      

    // Случай 2: Теперь найдите максимальную сумму, которая включает

    // угловые элементы.

    int max_wrap = 0, i; 

    for (i = 0; i < n; i++) 

    

            max_wrap += a[i]; // Вычисляем сумму массива

            a[i] = -a[i]; // инвертировать массив (изменить знак)

    

      

    // максимальная сумма с угловыми элементами будет:

    // массив-сумма - (-макс сумма подмассива инвертированного массива)

    max_wrap = max_wrap + kadane(a, n); 

      

    // Максимальная круговая сумма будет максимум двух сумм

    return (max_wrap > max_kadane)? max_wrap: max_kadane; 

  
// Стандартный алгоритм Кадане для поиска максимальной суммы подмассива
// Подробнее см. Https://www.geeksforgeeks.org/archives/576.

int kadane(int a[], int n) 

    int max_so_far = 0, max_ending_here = 0; 

    int i; 

    for (i = 0; i < n; i++) 

    

        max_ending_here = max_ending_here + a[i]; 

        if (max_ending_here < 0) 

            max_ending_here = 0; 

        if (max_so_far < max_ending_here) 

            max_so_far = max_ending_here; 

    

    return max_so_far; 

  
/ * Программа драйвера для тестирования maxCircularSum () * /

int main() 

    int a[] = {11, 10, -20, 5, -3, -5, 8, -13, 10}; 

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

    cout << "Maximum circular sum is " << maxCircularSum(a, n) << endl; 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// C-программа для задачи о максимальной непрерывной круговой сумме
#include<stdio.h>

  
// Стандартный алгоритм Кадане для поиска максимального подмассива
// сумма

int kadane(int a[], int n);

  
// Функция возвращает максимальную круговую непрерывную сумму
// в[]

int maxCircularSum(int a[], int n)

{

   // Случай 1: получить максимальную сумму с использованием стандартного kadane '

   // алгоритм

   int max_kadane = kadane(a, n);

  

   // Случай 2: Теперь найдите максимальную сумму, которая включает

   // угловые элементы.

   int max_wrap = 0, i;

   for (i=0; i<n; i++)

   {

        max_wrap += a[i]; // Вычисляем сумму массива

        a[i] = -a[i];  // инвертировать массив (изменить знак)

   }

  

   // максимальная сумма с угловыми элементами будет:

   // массив-сумма - (-макс сумма подмассива инвертированного массива)

   max_wrap = max_wrap + kadane(a, n);

  

   // Максимальная круговая сумма будет максимум двух сумм

   return (max_wrap > max_kadane)? max_wrap: max_kadane;

}

  
// Стандартный алгоритм Кадане для поиска максимальной суммы подмассива
// Подробнее см. Https://www.geeksforgeeks.org/archives/576.

int kadane(int a[], int n)

{

    int max_so_far = 0, max_ending_here = 0;

    int i;

    for (i = 0; i < n; i++)

    {

        max_ending_here = max_ending_here + a[i];

        if (max_ending_here < 0)

            max_ending_here = 0;

        if (max_so_far < max_ending_here)

            max_so_far = max_ending_here;

    }

    return max_so_far;

}

  
/ * Программа драйвера для тестирования maxCircularSum () * /

int main()

{

    int a[] =  {11, 10, -20, 5, -3, -5, 8, -13, 10};

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

    printf("Maximum circular sum is %dn",

                              maxCircularSum(a, n));

    return 0;

}

Джава

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

import java.io.*;

import java.util.*;

  

class MaxCircularSum

{

    // Функция возвращает максимальную круговую непрерывную сумму

    // в[]

    static int maxCircularSum (int a[])

    {

        int n = a.length;

  

        // Случай 1: получить максимальную сумму с использованием стандартного kadane '

        // алгоритм

        int max_kadane = kadane(a);

  

        // Случай 2: Теперь найдите максимальную сумму, которая включает

        // угловые элементы.

        int max_wrap  =  0;

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

        {

            max_wrap += a[i]; // Вычисляем сумму массива

            a[i] = -a[i];  // инвертировать массив (изменить знак)

        }

  

        // максимальная сумма с угловыми элементами будет:

        // массив-сумма - (-макс сумма подмассива инвертированного массива)

        max_wrap = max_wrap + kadane(a);

  

        // Максимальная круговая сумма будет максимум двух сумм

        return (max_wrap > max_kadane)? max_wrap: max_kadane;

    }

  

    // Стандартный алгоритм Кадане для поиска максимальной суммы подмассива

    // Подробнее см. Https://www.geeksforgeeks.org/archives/576.

    static int kadane (int a[])

    {

        int n = a.length;

        int max_so_far = 0, max_ending_here = 0;

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

        {

            max_ending_here = max_ending_here + a[i];

            if (max_ending_here < 0)

                max_ending_here = 0;

            if (max_so_far < max_ending_here)

                max_so_far = max_ending_here;

        }

        return max_so_far;

    }

  

    public static void main (String[] args)

    {

        int a[] =  {11, 10, -20, 5, -3, -5, 8, -13, 10};

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

                            maxCircularSum(a));

    }

} / * Этот код предоставлен Девешом Агравалом * /

питон

# Python-программа для задачи о максимальной непрерывной круговой сумме

  
# Стандартный алгоритм Кадане для поиска максимальной суммы подмассива

def kadane(a):

    n = len(a)

    max_so_far = 0

    max_ending_here = 0

    for i in range(0, n):

        max_ending_here = max_ending_here + a[i]

        if (max_ending_here < 0):

            max_ending_here = 0

        if (max_so_far < max_ending_here):

            max_so_far = max_ending_here

    return max_so_far

  
# Функция возвращает максимальную круговую непрерывную сумму в
# a []

def maxCircularSum(a):

  

    n = len(a)

  

    # Случай 1: получить максимальную сумму, используя стандартные каданы

    # алгоритм

    max_kadane = kadane(a)

  

    # Случай 2: Теперь найдите максимальную сумму, которая включает в себя угол

    # элементы.

    max_wrap = 0

    for i in range(0,n):

        max_wrap += a[i]

        a[i] = -a[i]

  

    Максимальная сумма с угловыми элементами будет:

    # массив-сумма - (-макс сумма подмассива инвертированного массива)

    max_wrap = max_wrap + kadane(a)

  

    # Максимальная круговая сумма будет не более двух сумм

    if max_wrap > max_kadane:

        return max_wrap

    else:

        return max_kadane

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

a = [11, 10, -20, 5, -3, -5, 8, -13, 10]

print "Maximum circular sum is", maxCircularSum(a)

  
# Этот код предоставлен Девешом Агравалом

C #

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

using System;

  

class MaxCircularSum {

      

    // Функция возвращает максимальный круговой

    // непрерывная сумма в []

    static int maxCircularSum(int[] a)

    {

        int n = a.Length;

  

        // Случай 1: получить максимальную сумму с использованием стандартного kadane '

        // алгоритм

        int max_kadane = kadane(a);

  

        // Случай 2: Теперь найдите максимальную сумму, которая включает

        // угловые элементы.

        int max_wrap = 0;

        for (int i = 0; i < n; i++) {

            max_wrap += a[i]; // Вычисляем сумму массива

            a[i] = -a[i]; // инвертировать массив (изменить знак)

        }

  

        // максимальная сумма с угловыми элементами будет:

        // массив-сумма - (-макс сумма подмассива инвертированного массива)

        max_wrap = max_wrap + kadane(a);

  

        // Максимальная круговая сумма будет максимум двух сумм

        return (max_wrap > max_kadane) ? max_wrap : max_kadane;

    }

  

    // Стандартный алгоритм Кадане для поиска максимальной суммы подмассива

    // Подробнее см. Https://www.geeksforgeeks.org/archives/576.

    static int kadane(int[] a)

    {

        int n = a.Length;

        int max_so_far = 0, max_ending_here = 0;

        for (int i = 0; i < n; i++) {

            max_ending_here = max_ending_here + a[i];

            if (max_ending_here < 0)

                max_ending_here = 0;

            if (max_so_far < max_ending_here)

                max_so_far = max_ending_here;

        }

        return max_so_far;

    }

      

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

    public static void Main()

    {

        int[] a = { 11, 10, -20, 5, -3, -5, 8, -13, 10 };

          

        Console.Write("Maximum circular sum is "

                               maxCircularSum(a));

    }

}

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

PHP

<?php

  
// PHP программа для максимума
// непрерывная задача о круговой сумме

  
// Функция возвращает максимум
// круговая непрерывная сумма $ a []

function maxCircularSum($a, $n

    // Случай 1: получить максимальную сумму

    // используя стандартный алгоритм Кадане

    $max_kadane = kadane($a, $n); 

      

    // Случай 2: теперь найти максимум

    // сумма, включающая угловые элементы.

    $max_wrap = 0;

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

    

            $max_wrap += $a[$i]; // Вычисляем сумму массива

            $a[$i] = -$a[$i]; // инвертировать массив (изменить знак)

    

      

    // максимальная сумма с угловыми элементами будет:

    // массив-сумма - (-макс сумма подмассива инвертированного массива)

    $max_wrap = $max_wrap + kadane($a, $n); 

      

    // Максимальная круговая сумма будет максимум двух сумм

    return ($max_wrap > $max_kadane)? $max_wrap: $max_kadane

  
// Стандартный алгоритм Кадане для
// найти максимальную сумму подмассива
// Подробнее см. Https://www.geeksforgeeks.org/archives/576.

function kadane($a, $n

    $max_so_far = 0;

    $max_ending_here = 0; 

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

    

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

        if ($max_ending_here < 0) 

            $max_ending_here = 0; 

        if ($max_so_far < $max_ending_here

            $max_so_far = $max_ending_here

    

    return $max_so_far

  

    / * Код водителя * /

    $a = array(11, 10, -20, 5, -3, -5, 8, -13, 10); 

    $n = count($a);

    echo "Maximum circular sum is ". maxCircularSum($a, $n); 

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

Выход:

Maximum circular sum is 31

Сложность времени: O (n), где n — количество элементов во входном массиве.

Обратите внимание, что приведенный выше алгоритм не работает, если все числа отрицательны, например, {-1, -2, -3}. В этом случае возвращается 0. Этот случай может быть обработан путем добавления предварительной проверки, чтобы увидеть, все ли числа отрицательны перед запуском вышеупомянутого алгоритма.

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

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

Максимальная круговая сумма подмассива

0.00 (0%) 0 votes