Рубрики

Максимальная сумма подмассива с использованием алгоритма «разделяй и властвуй»

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

Например, если заданный массив равен {-2, -5, 6, -2, -3, 1, 5 , -6}, то максимальная сумма подмассива равна 7 (см. Выделенные элементы).

Наивный метод — запустить две петли. Внешний цикл выбирает начальный элемент, внутренний цикл находит максимально возможную сумму с первым элементом, выбранным внешним циклом, и сравнивает этот максимум с общим максимумом. Наконец верните общий максимум. Временная сложность метода Наивного составляет O (n ^ 2).

Используя подход « Разделяй и властвуй» , мы можем найти максимальную сумму подмассива за время O (nLogn). Ниже приведен алгоритм «Разделяй и властвуй».

1) Разделите данный массив на две половины
2) Вернуть максимум следующих трех
…. а) Максимальная сумма подмассива в левой половине (сделать рекурсивный вызов)
…. б) Максимальная сумма подмассива в правой половине (сделать рекурсивный вызов)
…. c) Максимальная сумма подмассива, так что подрешетка пересекает среднюю точку

Строки 2.a и 2.b являются простыми рекурсивными вызовами. Как найти максимальную сумму подмассива, чтобы подмассив пересекал среднюю точку? Мы можем легко найти сумму пересечения в линейном времени. Идея проста: найти максимальную сумму, начиная с середины и заканчивая в некоторой точке слева от середины, затем найти максимальную сумму, начиная с середины + 1 и заканчивая точкой суммы справа от середины + 1. Наконец, объедините два и вернуться.

C ++

// Программа «Разделяй и властвуй» для задачи о максимальной сумме подмассива
#include <stdio.h>
#include <limits.h>

  
// Функция утилиты для поиска максимум двух целых

int max(int a, int b) { return (a > b)? a : b; }

  
// Функция утилиты для поиска максимум трех целых

int max(int a, int b, int c) { return max(max(a, b), c); }

  
// Находим максимально возможную сумму в arr [], так как arr [m] является ее частью

int maxCrossingSum(int arr[], int l, int m, int h)

{

    // Включаем элементы слева от середины.

    int sum = 0;

    int left_sum = INT_MIN;

    for (int i = m; i >= l; i--)

    {

        sum = sum + arr[i];

        if (sum > left_sum)

          left_sum = sum;

    }

  

    // Включить элементы справа от середины

    sum = 0;

    int right_sum = INT_MIN;

    for (int i = m+1; i <= h; i++)

    {

        sum = sum + arr[i];

        if (sum > right_sum)

          right_sum = sum;

    }

  

    // Возвращаем сумму элементов слева и справа от середины

    return left_sum + right_sum;

}

  
// Возвращает сумму подмассива максимальной суммы в aa [l..h]

int maxSubArraySum(int arr[], int l, int h)

{

   // Базовый случай: только один элемент

   if (l == h)

     return arr[l];

  

   // Найти среднюю точку

   int m = (l + h)/2;

  

   / * Вернуть максимум из следующих трех возможных случаев

      а) Максимальная сумма подмассива в левой половине

      б) Максимальная сумма подмассива в правой половине

      c) Максимальная сумма подмассива, такая, что подрешетка пересекает среднюю точку * /

   return max(maxSubArraySum(arr, l, m),

              maxSubArraySum(arr, m+1, h),

              maxCrossingSum(arr, l, m, h));

}

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

int main()

{

   int arr[] = {2, 3, 4, 5, 7};

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

   int max_sum = maxSubArraySum(arr, 0, n-1);

   printf("Maximum contiguous sum is %dn", max_sum);

   getchar();

   return 0;

}

Джава

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

import java.util.*;

  

class GFG {

  

    // Находим максимально возможную сумму в arr []

    // такой, что arr [m] является его частью

    static int maxCrossingSum(int arr[], int l,

                                int m, int h)

    {

        // Включаем элементы слева от середины.

        int sum = 0;

        int left_sum = Integer.MIN_VALUE;

        for (int i = m; i >= l; i--)

        {

            sum = sum + arr[i];

            if (sum > left_sum)

            left_sum = sum;

        }

  

        // Включить элементы справа от середины

        sum = 0;

        int right_sum = Integer.MIN_VALUE;

        for (int i = m + 1; i <= h; i++)

        {

            sum = sum + arr[i];

            if (sum > right_sum)

            right_sum = sum;

        }

  

        // Возвращаем сумму элементов слева

        // и справа от середины

        return left_sum + right_sum;

    }

  

    // Возвращает сумму подмассива максимальной суммы

    // в аа [л..ч]

    static int maxSubArraySum(int arr[], int l, 

                                      int h)

    {

    // Базовый случай: только один элемент

    if (l == h)

        return arr[l];

  

    // Найти среднюю точку

    int m = (l + h)/2;

  

    / * Вернуть максимум следующих трех

    Возможные случаи:

    а) Максимальная сумма подмассива в левой половине

    б) Максимальная сумма подмассива в правой половине

    c) Максимальная сумма подмассива, такая что

    подрешетка пересекает среднюю точку * /

    return Math.max(Math.max(maxSubArraySum(arr, l, m),

                    maxSubArraySum(arr, m+1, h)),

                    maxCrossingSum(arr, l, m, h));

    }

  

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

    public static void main(String[] args)

    {

    int arr[] = {2, 3, 4, 5, 7};

    int n = arr.length;

    int max_sum = maxSubArraySum(arr, 0, n-1);

      

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

                                         max_sum);

    }

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

python3

# Программа «Разделяй и властвуй»
# для проблемы максимальной суммы подмассива

  
# Найти максимально возможную сумму в
# arr [] ах, что arr [m] является его частью

def maxCrossingSum(arr, l, m, h) :

      

    # Включить элементы слева от середины.

    sm = 0; left_sum = -10000

      

    for i in range(m, l-1, -1) :

        sm = sm + arr[i]

          

        if (sm > left_sum) :

            left_sum = sm

      

      

    # Включить элементы справа от середины

    sm = 0; right_sum = -1000

    for i in range(m + 1, h + 1) :

        sm = sm + arr[i]

          

        if (sm > right_sum) :

            right_sum = sm

      

  

    # Вернуть сумму элементов слева и справа от середины

    return left_sum + right_sum;

  

  
# Возвращает сумму подмассива максимальной суммы в aa [l..h]

def maxSubArraySum(arr, l, h) :

      

    # Базовый случай: только один элемент

    if (l == h) :

        return arr[l]

  

    # Найти среднюю точку

    m = (l + h) // 2

  

    # Вернуть максимум из следующих трех возможных случаев

    # a) Максимальная сумма подмассива в левой половине

    # б) Максимальная сумма подмассива в правой половине

    # c) Максимальная сумма подмассива такая, что

    # подрешетка пересекает среднюю точку

    return max(maxSubArraySum(arr, l, m),

               maxSubArraySum(arr, m+1, h),

               maxCrossingSum(arr, l, m, h))

              

  
Код водителя

arr = [2, 3, 4, 5, 7]

n = len(arr)

  

max_sum = maxSubArraySum(arr, 0, n-1)

print("Maximum contiguous sum is ", max_sum)

  
# Этот код предоставлен Никитой Тивари.

C #

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

using System;

  

class GFG {

  

    // Находим максимально возможную сумму в arr []

    // такой, что arr [m] является его частью

    static int maxCrossingSum(int []arr, int l,

                                int m, int h)

    {

        // Включаем элементы слева от середины.

        int sum = 0;

        int left_sum = int.MinValue;

        for (int i = m; i >= l; i--)

        {

            sum = sum + arr[i];

            if (sum > left_sum)

                left_sum = sum;

        }

  

        // Включить элементы справа от середины

        sum = 0;

        int right_sum = int.MinValue;;

        for (int i = m + 1; i <= h; i++)

        {

            sum = sum + arr[i];

            if (sum > right_sum)

                right_sum = sum;

        }

  

        // Возвращаем сумму элементов слева

        // и справа от середины

        return left_sum + right_sum;

    }

  

    // Возвращает сумму подмассива максимальной суммы

    // в аа [л..ч]

    static int maxSubArraySum(int []arr, int l, 

                                        int h)

    {

          

    // Базовый случай: только один элемент

    if (l == h)

        return arr[l];

  

    // Найти среднюю точку

    int m = (l + h)/2;

  

    / * Вернуть максимум следующих трех

    Возможные случаи:

    а) Максимальная сумма подмассива в левой половине

    б) Максимальная сумма подмассива в правой половине

    c) Максимальная сумма подмассива, такая что

    подрешетка пересекает среднюю точку * /

    return Math.Max(Math.Max(maxSubArraySum(arr, l, m),

                          maxSubArraySum(arr, m+1, h)),

                         maxCrossingSum(arr, l, m, h));

    }

  

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

    public static void Main()

    {

        int []arr = {2, 3, 4, 5, 7};

        int n = arr.Length;

        int max_sum = maxSubArraySum(arr, 0, n-1);

          

        Console.Write("Maximum contiguous sum is "+

                                            max_sum);

    }

}

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

PHP

<?php
// Программа «Разделяй и властвуй»
// для задачи максимальной суммы подмассива

  
// Находим максимально возможную сумму в arr []
// такой, что arr [m] является его частью

function maxCrossingSum(&$arr, $l, $m, $h

    // Включаем элементы слева от середины.

    $sum = 0; 

    $left_sum = PHP_INT_MIN; 

    for ($i = $m; $i >= $l; $i--) 

    

        $sum = $sum + $arr[$i]; 

        if ($sum > $left_sum

        $left_sum = $sum

    

  

    // Включить элементы справа от середины

    $sum = 0; 

    $right_sum = PHP_INT_MIN; 

    for ($i = $m + 1; $i <= $h; $i++) 

    

        $sum = $sum + $arr[$i]; 

        if ($sum > $right_sum

        $right_sum = $sum

    

  

    // Возвращаем сумму элементов слева

    // и справа от середины

    return $left_sum + $right_sum

  
// Возвращает сумму максимальной суммы
// подрешетка в aa [l..h]

function maxSubArraySum(&$arr, $l, $h

    // Базовый случай: только один элемент

    if ($l == $h

        return $arr[$l]; 

      

    // Найти среднюю точку

    $m = intval(($l + $h) / 2); 

      

    / * Вернуть максимум из следующих трех возможных случаев

        а) Максимальная сумма подмассива в левой половине

        б) Максимальная сумма подмассива в правой половине

        c) Максимальная сумма подмассива, такая что

           подрешетка пересекает среднюю точку * /

    return max(maxSubArraySum($arr, $l, $m), 

               maxSubArraySum($arr, $m + 1, $h), 

               maxCrossingSum($arr, $l, $m, $h)); 

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

$arr = array(2, 3, 4, 5, 7); 

$n = count($arr); 

$max_sum = maxSubArraySum($arr, 0, $n - 1); 

echo "Maximum contiguous sum is " . $max_sum

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


Выход :

Maximum contiguous sum is 21

Сложность времени: maxSubArraySum () является рекурсивным методом, а сложность времени может быть выражена в виде следующего рекуррентного отношения.
T (n) = 2T (n / 2) + Θ (n)
Вышеупомянутое повторение аналогично сортировке слиянием и может быть решено с использованием метода дерева повторений или основного метода. Это относится к случаю II Master Method, и решением рецидива является Θ (nLogn).

Алгоритм Кадана для этой задачи занимает O (n) времени. Поэтому алгоритм Кадане лучше, чем подход «Разделяй и властвуй», но эту проблему можно рассматривать как хороший пример для демонстрации силы Разделяй и властвуй. Приведенный выше простой подход, при котором мы делим массив на две половины, уменьшает временную сложность с O (n ^ 2) до O (nLogn).

Ссылки:
Введение в алгоритмы от Клиффорда Стейна, Томаса Х. Кормена, Чарльза Э. Лизерсона, Рональда Л.

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

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

Максимальная сумма подмассива с использованием алгоритма «разделяй и властвуй»

0.00 (0%) 0 votes