Kadenceov algoritam: Susjedni podniz s najvećim zbrojem

Koji je najveći zbroj kontinuiranog podniza?

Podniz je kontinuirani dio niza. To može biti jedan element niza ili neki dio niza. Susjedni podniz najvećeg zbroja znači podniz koji ima najveću vrijednost zbroja.

Na primjer, niz je {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Njegovi podnizovi mogu biti: {-10,5,1,6} ili {5,1,6} ili {2,7,3, -5} itd. Ali {5,1,6,3} ne može biti podniz jer ne održavaju nizove.

Ako primijetite, među svim podnizovima, sljedeći označeni podnizovi (5,1,6) imaju najveću vrijednost zbroja:

Zbroj podniza {5,1,6} = 11 je najveći zbroj u svim mogućim kombinacijama podniza gornjeg niza. Dakle, za gornji niz, maksimalni podniz je {5,1,6}.

Kadenceov algoritam: Susjedni podniz s najvećim zbrojem

Jednostavan pristup rješavanju kontinuiranog podniza najvećeg zbroja

Jednostavan način rješavanja ovog problema je korištenje dvije petlje za pronalaženje svih podnizova, izračunavanje zbroja, a zatim pronalaženje njegove maksimalne vrijednosti.

Evo dijagrama toka za jednostavan pristup pronalaženju najvećeg sumskog kontinuiranog podniza. Ovo je brutalni pristup jer prolazimo kroz sve moguće podnizove.

Evo jednostavnih koraka za to.

Korak 1) Inicijalizirajte max_sum minimalnom vrijednošću cijelog broja i dodijelite varijablama "begin" i "end" s nulom.

Korak 2) Neka su i i j indeksi niza, gdje je "j" veće od jednakog "i". Predstavlja početni indeks podniza, a "j" predstavlja završni indeks podniza.

Korak 3) “Current_sum” će sadržavati zbroj podniza. Nakon izračunavanja trenutnog zbroja, provjerite je li current_sum veći od max_sum.

Korak 4) Ako je current_sum veći, onda zamijenite max_sum trenutnim zbrojem.

Korak 5) Provjerite dolazi li "j" do kraja niza ili ne. Ako “j” dosegne kraj niza, zatim povećajte “i” i promijenite vrijednost current_sum na 0.

Korak 6) Izvedite sve ove korake, dok "i" ne dođe do kraja niza.

Korak 7) Na kraju ove dvije petlje, max_sum će sadržavati najveću sumu podniza.

Pseudo kod za jednostavan pristup

  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++ Implementacija jednostavnog pristupa

#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]));
}

Izlaz:

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

Python Primjena jednostavnog pristupa

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)

Izlaz:

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

Kadaneov algoritam za pronalaženje najvećeg sumskog kontinuiranog podniza

Kadaneov algoritam je vrsta metode "dinamičkog programiranja". Ovdje ćemo koristiti jednu petlju umjesto dvije petlje. Opća implementacija Kadaneovog algoritma radi samo za pozitivne nizove brojeva.

Trebaju nam samo dvije varijable da pronađemo najveći sumski susjedni podniz. Evo dijagrama toka za Kadaneov algoritam:

Evo koraka za Kadaneov algoritam:

Korak 1) Napravite dvije varijable, current_sum i max_sum.

“Current_sum” će zadržati vrijednost maksimalnog zbroja koji završava u određenom indeksu polja, dok će “max_sum” pohraniti maksimalnu vrijednost zbroja do sada.

Korak 2) Dodat ćemo vrijednost s current_sum za svaki element niza. Zatim ćemo provjeriti dva uvjeta u nastavku:

• Ako je current_sum manji od trenutnog elementa, tada će vrijednost current_sum biti trenutni element.
• Ako je max_sum manji od current_sum, tada će max_sum biti current_sum.

Korak 3) Izvođenjem prethodnog koraka za cijeli niz, imat ćemo najveći zbroj kontinuiranog podniza u varijabli "max_sum".

Primjer Kadaneovog algoritma

Demonstrirat ćemo Kadanesov algoritam s nizom male veličine i raspravljati o svakom koraku pronalaženja najvećeg zbroja susjednog podniza.

Pretpostavimo da je dani niz ovakav:

Evo koraka Kadaneovog algoritma:

Korak 1) Napravite dvije varijable, current_sum i max_sum. Dodijelite INT_MIN max_sum i nulu current_sum. (Ovdje INT_MIN znači minimalni cijeli broj).

Korak 2) Kod indeksa 0, vrijednost je 4. Dakle, current_sum = 0 + 4 ili 4. Ovdje je current_sum veći od max_sum, max_sum će biti 4.

Korak 3) Kod indeksa 1 vrijednost je -2. Dakle, current_sum = 4 + (-2) ili 2.

Ovaj put current_sum je manji od max_sum. Kao rezultat toga, vrijednost max_sum neće biti ažurirana.

Korak 4) Sljedeća vrijednost je 1. Ako ovo zbrojimo s current_sum, tada će current_sum biti 3. Ipak, max_sum je veći od current_sum. Dakle, max_sum neće biti ažuriran.

Korak 5) Kod indeksa 3, vrijednost je tri. Ažurirat ćemo vrijednost povećanjem current_sum za 3. Dakle, current_sum će biti 6.

U ovom slučaju, max_sum je manji od current_sum. Dakle, max_sum će se ažurirati s vrijednošću current_sum.

Korak 6) Za zadnji element niza, imamo -1. Ako ovo zbrojimo s current_sum, current_sum će biti 5, što je manje od max_sum. Dakle, max_sum će ostati 6.

Kako smo došli do kraja niza, algoritam ovdje završava. Sada, "max_sum" sadrži maksimalnu podnizu zbroja. Što je 5. Podniz je {4,-2,1,3}.

Pseudo kod za Kadaneov algoritam

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++Implementacija Kadaneovog algoritma

#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]));
}

Izlaz:

largest sum is 12

Python Implementacija Kadaneovog algoritma

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])

Izlaz:

largest sum is 12

Analiza složenosti za najveći sumski kontinuirani podniz

Jednostavan pristup koristi dvije petlje. Ta metoda izračunava sve moguće zbrojeve podniza kako bi pronašla najveći. To je pristup grube sile. Svaka petlja se izvodi do kraja poredak.

Ako niz ima ukupno N elemenata, tada ćemo pomoću dvije petlje proći kroz N² elementi. Kao rezultat toga, vremenska složenost za jednostavan pristup za pronalaženje najvećeg zbroja susjednog podniza bit će O(N2). Ovdje "O" označava funkciju složenosti.

S druge strane, Kadaneov algoritam je metoda dinamičkog programiranja za pronalaženje maksimalnog kontinuiranog podniza zbroja. Ako slijedite primjer ili kod, vidjet ćete da koristimo samo jednu petlju.

Kao rezultat toga, ako ulazni niz ima veličinu od N, tada će vremenska složenost Kadaneovog algoritma biti O(N). Ovo je brže od jednostavnog pristupa. Na primjer, niz koji sadrži 100 elemenata. Jednostavan pristup će uzeti 100*100 ili 10,000 100 CPU vremena. Ali Kadaneov algoritam će uzeti samo XNUMX CPU vremena.