Алгоритъмът на Kadence: Най-голямата сума непрекъснат подмасив

Какъв е най-големият сборен непрекъснат подмасив?

Подмасивът е непрекъсната част от масив. Може да бъде отделен елемент от масив или някаква част от масива. Непрекъснатият подмасив с най-голяма сума означава подмасив, който има максимална сумарна стойност.

Например масивът е {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Неговите подмасиви могат да бъдат: {-10,5,1,6} или {5,1,6} или {2,7,3, -5} и т.н. Но {5,1,6,3} не може да бъде подмасив, защото не поддържат последователностите.

Ако забележите, сред всички подмасиви, следният подчертан подмасив (5,1,6) има максимална сумирана стойност:

Сумата от подмасива {5,1,6} = 11 е максималната сума във всички възможни комбинации от подмасив от горния масив. И така, за горния масив максималният подмасив е {5,1,6}.

Алгоритъмът на Kadence: Най-голямата сума непрекъснат подмасив

Прост подход за решаване на съседен подмасив с най-голяма сума

Простият начин за решаване на този проблем е да използвате два цикъла, за да намерите всички подмасиви, да изчислите сумата и след това да намерите нейната максимална стойност.

Ето блок-схемата за простия подход за намиране на най-голямата сума непрекъснат подмасив. Това е подход на груба сила, тъй като преминаваме през всички възможни подмасиви.

Ето простите стъпки за това.

Стъпка 1) Инициализирайте max_sum с минимална целочислена стойност и задайте променливи „begin“ и „end“ с нула.

Стъпка 2) Нека i и j са индексът на масива, където „j“ е по-голямо от равно на „i“. Той представлява началния индекс на подмасива, а „j“ представлява крайния индекс на подмасива.

Стъпка 3) “Current_sum” ще съдържа сумата на подмасива. След като изчислите текущата сума, проверете дали current_sum е по-голяма от max_sum.

Стъпка 4) Ако текущата_сума е по-голяма, тогава заменете max_sum с текущата сума.

Стъпка 5) Проверете дали „j“ достига края на масива или не. Ако „j“ достигне края на масива, тогава увеличете „i“ и променете стойността на current_sum на 0.

Стъпка 6) Изпълнете всички тези стъпки, докато "i" достигне края на масива.

Стъпка 7) В края на тези два цикъла max_sum ще съдържа най-голямата сума на подмасив.

Псевдо код за прост подход

  function maximumSubarraySum():
    input: array
  for all possible subArray from array:
    calculate sum of each sub array
    store the maximum subArray
  return the maximum sum

C++ Прилагане на прост подход

#include <stdio.h>
#include <iostream>
using namespace std;
void maximumSubarraySum(int array[], int n) {
  int max_sum = -1e9;
  int begin = 0;
  int end = 0;
  for (int i = 0; i < n; i++) {
    int current_sum = 0;
    for (int j = i; j < n; j++) {
      current_sum += array[j];
      if (max_sum < current_sum) {
        max_sum = current_sum;
        begin = i;
        end = j;
      }
    }
  }
  cout << "largest sum is " << max_sum << endl;
  cout << "largest sum contiguous subarray: ";
  for (int i = begin; i <= end; i++) {
    cout << array[i] << "\t";
  }
}
int main() {
  int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
  maximumSubarraySum(array, sizeof(array) / sizeof(array[0]));
}

Изход:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Python Прилагане на прост подход

def maximumSubarraySum(numbers):
max_sum,begin,end = -1e9, 0 , 0
  for i in range(len(numbers)):
    current_sum=0
  for j in range(i,len(numbers)):
    current_sum+=numbers[j]
  if max_sum<current_sum:
    max_sum=current_sum
  begin,end=i,j
    print("largest sum is ",max_sum)
    print("largest sum contiguous subarray: ",end="")
  for i in range(begin,end+1):
    print(numbers[i],end='\t')
    numbers = [-10,5,1,6,-9,2,-7,3,-5]
    maximumSubarraySum(numbers)

Изход:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Алгоритъмът на Кадане за намиране на най-големия сборен непрекъснат подмасив

Алгоритъмът на Кадане е вид метод на "динамично програмиране". Тук ще използваме един цикъл вместо два цикъла. Общата реализация на алгоритъма на Kadane работи само за масиви с положителни числа.

Нуждаем се само от две променливи, за да намерим най-големия сборен съседен подмасив. Ето блок-схемата за алгоритъма на Kadane:

Ето стъпките за алгоритъма на Кадане:

Стъпка 1) Създайте две променливи, current_sum и max_sum.

„Current_sum“ ще запази стойността на максималната сума, която завършва в конкретен индекс на масив, докато „max_sum“ ще запази максималната сумирана стойност досега.

Стъпка 2) Ще добавим стойността с текущата_сума за всеки елемент от масива. След това ще проверим две условия по-долу:

• Ако current_sum е по-малко от текущия елемент, тогава стойността на current_sum ще бъде текущият елемент.
• Ако max_sum е по-малко от current_sum, тогава max_sum ще бъде current_sum.

Стъпка 3) Изпълнявайки предишната стъпка за целия масив, ще имаме най-голямата сума непрекъснат подмасив в променливата „max_sum“.

Пример за алгоритъм на Кадане

Ще демонстрираме алгоритъма на Каданес с малък по размер масив и ще обсъдим всяка стъпка за намиране на най-големия сборен непрекъснат подмасив.

Да приемем, че даденият масив е като следния:

Ето стъпките на алгоритъма на Кадане:

Стъпка 1) Създайте две променливи, current_sum и max_sum. Присвоете INT_MIN на max_sum и нула на current_sum. (Тук INT_MIN означава минималното цяло число).

Стъпка 2) При индекс 0 стойността е 4. Така че current_sum = 0 + 4 или 4. Тук current_sum е по-голямо от max_sum, max_sum ще бъде 4.

Стъпка 3) При индекс 1 стойността е -2. И така, текущата_сума = 4 + (-2) или 2.

Този път текущата_сума е по-малка от максималната_сума. В резултат на това стойността на max_sum няма да бъде актуализирана.

Стъпка 4) Следващата стойност е 1. Ако добавим това с текущата_сума, тогава текущата_сума ще бъде 3. Все пак максималната_сума е по-голяма от текущата_сума. Така че max_sum няма да се актуализира.

Стъпка 5) При индекс 3 стойността е три. Ще актуализираме стойността, като увеличим текущата_сума с 3. Така че текущата_сума ще бъде 6.

В този случай max_sum е по-малък от current_sum. Така че max_sum ще бъде актуализиран със стойността на current_sum.

Стъпка 6) За последния елемент от масива имаме -1. Ако добавим това с current_sum, current_sum ще бъде 5, което е по-малко от max_sum. Така че max_sum ще остане 6.

Когато стигнахме до края на масива, алгоритъмът свършва тук. Сега „max_sum“ съдържа подмасива с максимална сума. Което е 5. Подмасивът е {4,-2,1,3}.

Псевдокод за алгоритъма на Кадан

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each elements in array:
        add the element with current_sum
        if current_sum is greater than the maximum_sum
            then maximum_sum = current_sum
        if current_sum is less than the element
            then current_sum = element
    return the value of maximum_sum

C++Реализация на алгоритъма на Кадане

#include < iostream >
using namespace std;
void kadane(int array[], int n) {
  int current_sum = 0;
  int max_sum = -1e9;
  // -1e9 means -10000000
  for (int i = 0; i < n; i++) {
    current_sum += array[i];
    if (max_sum < current_sum) {
      max_sum = current_sum;
    }
    if (current_sum < array[i]) {
      current_sum = array[i];
    }
  }
  cout << "largest sum is " << max_sum << endl;
}
int main() {
  int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
  kadane(array, sizeof(array) / sizeof(array[0]));
}

Изход:

largest sum is 12

Python Реализация на алгоритъма на Кадане

def kadane(numbers):
  current_sum = 0
  max_sum = -1e9
for i in range(len(numbers)):
  current_sum += numbers[i]
if max_sum < current_sum:
  max_sum = current_sum
if current_sum<numbers[i]:
  current_sum = numbers[i]
  print("largest sum is ",max_sum)
  kadane([-10,5,1,6,-9,2,-7,3,-5])

Изход:

largest sum is 12

Анализ на сложността за най-голям сборен непрекъснат подмасив

Простият подход използва два цикъла. Този метод изчислява всички възможни суми на подмасиви, за да намери най-голямата. Това е подход на груба сила. Всеки цикъл се изпълнява до края на масив.

Ако даден масив има общо N елементи, тогава използвайки два цикъла, ще преминем през N² елементи. В резултат на това времевата сложност за прост подход за намиране на най-голямата сума непрекъснат подмасив ще бъде O(N2). Тук "O" означава функцията на сложността.

От друга страна, алгоритъмът на Кадане е методът за динамично програмиране за намиране на максималния непрекъснат подмасив на сумата. Ако следвате примера или кода, ще видите, че използваме само един цикъл.

В резултат на това, ако входният масив има размер от N, тогава времевата сложност на алгоритъма на Кадан ще бъде O(N). Това е по-бързо от простия подход. Например масив, съдържащ 100 елемента. Простият подход ще отнеме 100*100 или 10,000 100 процесорно време. Но алгоритъмът на Kadane ще отнеме само XNUMX процесорно време.