Algoritmul lui Kadence: Cea mai mare sumă Subbarray contiguă
Sarah Chen
Care este cea mai mare sumă adiacentă?
Un subbary este o parte continuă a unui tablou. Poate fi un singur element al unei matrice sau o fracțiune a matricei. Cea mai mare sumă adiacentă înseamnă o sumă care are valoarea maximă a sumei.
De exemplu, o matrice este {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Sub-matricele sale pot fi: {-10,5,1,6} sau {5,1,6} sau {2,7,3, -5} etc. Dar {5,1,6,3} nu poate fi un subbary deoarece nu mențin secvențele.
Dacă observați că, dintre toate subgrupurile, următoarea subbarra evidențiată (5,1,6) are valoarea maximă de însumare:
Suma subgrupului {5,1,6} = 11, este suma maximă în toate combinațiile posibile de subgrup din tabloul de mai sus. Deci, pentru matricea de mai sus, subbarra maximă este {5,1,6}.
Algoritmul lui Kadence: Cea mai mare sumă Subbarray contiguă
Abordare simplă pentru rezolvarea celei mai mari sume subordonate
Modalitatea simplă de a rezolva această problemă este să folosiți două bucle pentru a găsi toate subbaryurile, calculați suma și apoi găsiți valoarea maximă a acesteia.
Iată diagrama fluxului pentru abordarea simplă de a găsi cea mai mare sumă sub-matrice contiguă. Aceasta este o abordare cu forță brută, deoarece trecem prin toate subbariile posibile.
Iată pașii simpli pentru a face acest lucru.
Pas 1) Inițializați suma_max cu o valoare întreagă minimă și atribuiți variabilele „begin” și „end” cu zero.
Pas 2) Fie i și j indicele matricei, unde „j” este mai mare decât egal cu „i”. Reprezintă indicele de început al subgrupului, iar „j” reprezintă indicele de sfârșit al subgrupului.
Pas 3) „Current_sum” va deține suma subbaryului. După calcularea sumei curente, verificați dacă suma_actuală este mai mare decât suma_max.
Pas 4) Dacă suma_actuală este mai mare, atunci înlocuiți suma_max cu suma curentă.
Pas 5) Verificați dacă „j” ajunge la sfârșitul matricei sau nu. Dacă „j” ajunge la sfârșitul matricei, apoi incrementați „i” și modificați valoarea current_sum la 0.
Pas 6) Efectuați toți acești pași, până când „i” ajunge la sfârșitul matricei.
Pas 7) La sfârșitul acestor două bucle, The max_sum va deține cea mai mare sumă subbary.
Pseudocod pentru abordare simplă
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++ Implementarea abordării simple
#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]));
}
ieșire:
largest sum is 12 largest sum contiguous subarray: 5 1 6
Python Implementarea unei abordări simple
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)
ieșire:
largest sum is 12 largest sum contiguous subarray: 5 1 6
Algoritmul lui Kadane pentru a găsi cea mai mare sumă adiacentă
Algoritmul lui Kadane este un fel de metodă de „programare dinamică”. Aici vom folosi o buclă în loc de două bucle. Implementarea generală a algoritmului lui Kadane funcționează numai pentru matrice de numere pozitive.
Avem nevoie doar de două variabile pentru a găsi cea mai mare sumă adiacentă. Iată diagrama de flux pentru algoritmul lui Kadane:
Iată pașii pentru algoritmul lui Kadane:
Pas 1) Creați două variabile, current_sum și max_sum.
„Current_sum” va păstra valoarea sumei maxime care se termină într-un anumit index de matrice, în timp ce „max_sum” va stoca valoarea maximă de însumare de până acum.
Pas 2) Vom adăuga valoarea cu current_sum pentru fiecare element de matrice. Apoi vom verifica două condiții mai jos:
- Dacă current_sum este mai mică decât elementul curent, atunci valoarea current_sum va fi elementul curent.
- Dacă max_sum este mai mică decât current_sum, atunci max_sum va fi current_sum.
Pas 3) Efectuând pasul anterior pentru întregul tablou, vom avea cea mai mare sumă subbarray contiguă din variabila „max_sum”.
Exemplu de algoritm al lui Kadane
Vom demonstra algoritmul lui Kadanes cu o matrice de dimensiuni reduse și vom discuta fiecare pas de găsire a celei mai mari sume subdivizate.
Să presupunem că tabloul dat este ca următorul:
Iată pașii algoritmului lui Kadane:
Pas 1) Creați două variabile, current_sum și max_sum. Atribuiți INT_MIN la suma_max și zero la suma_actuală. (Aici, INT_MIN înseamnă numărul întreg minim).
Pas 2) La indexul 0, valoarea este 4. Deci, suma_actuală = 0 + 4 sau 4. Aici suma_actuală este mai mare decât suma_max, suma_max va fi 4.
Pas 3) La indicele 1, valoarea este -2. Deci, suma_actuală = 4 + (-2) sau 2.
De data aceasta, suma_actuală este mai mică decât suma_max. Ca rezultat, valoarea lui max_sum nu va fi actualizată.
Pas 4) Următoarea valoare este 1. Dacă adăugăm aceasta cu suma_actuală, atunci suma_actuală va fi 3. Totuși, suma_max este mai mare decât suma_actuală. Deci, suma_max nu va fi actualizată.
Pas 5) La indicele 3, valoarea este trei. Vom actualiza valoarea incrementând suma_actuală cu 3. Deci, suma_actuală va fi 6.
În acest caz, suma_max este mai mică decât suma_actuală. Deci, max_sum va fi actualizat cu valoarea current_sum.
Pas 6) Pentru ultimul element al matricei, avem -1. Dacă adăugăm acest lucru cu current_sum, current_sum va fi 5, care este mai mic decât max_sum. Deci, suma maximă va rămâne 6.
Când am ajuns la sfârșitul matricei, algoritmul se termină aici. Acum, „max_sum” conține suma maximă a sumei. Care este 5. Subbarra este {4,-2,1,3}.
Pseudocod pentru algoritmul lui Kadane
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++Implementarea algoritmului lui Kadane
#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]));
}
ieșire:
largest sum is 12
Python Implementarea algoritmului lui Kadane
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])
ieșire:
largest sum is 12
Analiza complexității pentru cea mai mare sumă de subbaraj contigu
Abordarea simplă folosește două bucle. Această metodă calculează toate sumele posibile pentru a găsi cea mai mare. Este o abordare cu forță brută. Fiecare buclă rulează până la sfârșitul mulțime.
Dacă o matrice are un total de N elemente, apoi folosind două bucle, vom trece prin N2 elemente. Ca rezultat, complexitatea de timp pentru o abordare simplă pentru a găsi cea mai mare sumă sub-barra contiguă va fi O(N2). Aici, „O” înseamnă funcția de complexitate.
Pe de altă parte, algoritmul lui Kadane este metoda de programare dinamică pentru a găsi suma maximă contigua. Dacă urmați exemplul sau codul, veți vedea că folosim o singură buclă.
Ca rezultat, dacă matricea de intrare are o dimensiune de N, atunci complexitatea temporală a algoritmului lui Kadane va fi O(N). Aceasta este mai rapidă decât abordarea simplă. De exemplu, o matrice care conține 100 de elemente. Abordarea simplă va dura 100*100 sau 10,000 de timp CPU. Dar algoritmul lui Kadane va dura doar 100 de timp CPU.
