Algoritmul lui Kadence: Cea mai mare sumă Subbarray contiguă

prin: Echipa editorială Echipa editorială
Hours Actualizat

⚡ Rezumat inteligent

Algoritmul lui Kadane găsește cea mai mare sumă a unui subarray continuu în timp liniar prin tracobținerea unui maxim în timp ce scanează fiecare submatrice posibilă. Acest truc clasic de programare dinamică alimentează problemele de acțiuni, finanțe și semnale.

  • 🎯 Definiția problemei: Un subarray contiguu este o secvență de elemente consecutive; scopul este subarray-ul cu cea mai mare sumă aritmetică din interiorul unui array mixt pozitiv și negativ.
  • 🐢 Forta bruta: Două bucle imbricate evaluează fiecare index de început și de sfârșit într-un timp de O(N²) și afișează fereastra câștigătoare folosind markeri de început și de sfârșit.
  • ⚡ Perspectiva lui Kadane: Resetează suma curentă ori de câte ori elementul curent bate acumulatorul, keeping doar cel mai bun prefix care ar putea încă să se transforme în răspuns.
  • 🧭 Exemplu lucrat: O scurtă trecere în revistă a unui tablou cu valori negative arată cum max_sum și current_sum evoluează pas cu pas până când este capturat maximul real.
  • 💻 Acoperire lingvistică: Ambele C++ și Python Implementările abordării simple și ale algoritmului lui Kadane demonstrează tranziția de la timpul O(N²) la timpul O(N).
  • 📊 Complexitate: Algoritmul lui Kadane rulează în timp O(N) cu O(1) spațiu suplimentar, depășind dramatic performanțele de bază ale algoritmului brute force pe tablouri de intrare mari.
Citește mai mult

Algoritmul lui Kadane cu cea mai mare sumă a unui subarray contiguu

Care este submatricea contiguă cu cea mai mare sumă?

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, luăm tabloul {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Subtablourile sale pot fi {-10, 5, 1, 6}, {5, 1, 6} sau {2, -7, 3, -5} și așa mai departe. Cu toate acestea, {5, 1, 6, 3} nu poate fi un subtablo deoarece elementele nu se află într-o secvență contiguă.

Cea mai mare sumă Subbarray contiguă

Dacă observați, dintre toate submatricile, submatricea evidențiată {5, 1, 6} are valoarea maximă de însumare:

Submatricea contiguă cu cea mai mare sumă evidențiată

Suma submatricii {5, 1, 6} este 12, suma maximă pentru toate submatricile posibile ale matricei de mai sus. Așadar, pentru această matrice, suma maximă a submatricii continue este {5, 1, 6}.

Abordare simplă pentru rezolvarea submatricei continue cu cea mai mare sumă

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ă schema logică pentru abordarea simplă de găsire a submatricii continue cu cea mai mare sumă. Aceasta este o abordare prin forță brută, deoarece parcurgem fiecare submatrice posibilă.

Abordare simplă pentru rezolvarea celei mai mari sume

Iată pașii simpli pentru a face acest lucru.

Pas 1) inițializa sumă_max cu valoarea întreagă minimă și setați începe și capăt la zero.

Pas 2) Lăsa i și j să fie indici de matrice unde j este mai mare sau egal cu i; i marchează începutul submatricei și j sfârșitul său.

Pas 3) sumă_actuală conține suma curentă. După fiecare actualizare, verificați dacă sumă_actuală este mai mare decât sumă_max.

Pas 4) If sumă_actuală este mai mare, înlocuiți sumă_max cu ea.

Pas 5) Atunci când j ajunge la sfârșitul matricei, incrementează i și resetați sumă_actuală la 0.

Pas 6) Repetați până când i ajunge la capătul matricei. sumă_max atunci deține cea mai mare sumă din subarray.

Pseudo Code pentru o abordare simplă

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        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 abordării 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
Nu ratați:

Algoritmul lui Kadane pentru a găsi cea mai mare sumă într-un subarray continuu

Algoritmul lui Kadane este o metodă de programare dinamică care folosește o singură buclă în loc de două. Acesta gestionează tablouri cu numere pozitive și negative mixte, atâta timp cât cel puțin o valoare este non-negativă.

Avem nevoie doar de două variabile pentru a găsi cea mai mare sumă a unui subarray continuu. Iată schema logică:

Algoritmul lui Kadane pentru a găsi cea mai mare sumă

Iată pașii pentru algoritmul lui Kadane:

Pas 1) Creați două variabile, sumă_actuală și sumă_max.

sumă_actuală păstrează suma maximă care se termină la un anumit index al matricei, în timp ce sumă_max stochează cea mai mare valoare a însumării observată până în prezent.

Pas 2) Adăugați fiecare element al matricei la sumă_actualăApoi verificați cele două condiții de mai jos:

  • If sumă_actuală este mai mic decât elementul curent, atunci sumă_actuală devine elementul curent.
  • If sumă_max e mai puțin decât sumă_actuală, Apoi sumă_max devine sumă_actuală.

Pas 3) După repetarea pasului anterior pentru întreaga matrice, sumă_max deține cea mai mare sumă dintr-un subarray contiguu.

Exemplu de algoritm al lui Kadane

Demonstrăm algoritmul lui Kadane pe un tablou mic și parcurgem fiecare pas pentru găsirea celui mai mare subtablou continuu cu sumă.

Să presupunem că matricea dată este de genul următor:

Exemplu de algoritm al lui Kadane

Iată pașii algoritmului lui Kadane:

Pas 1) Creați două variabile, sumă_actuală și sumă_maxAtribuiți INT_MIN la . sumă_max și zero până la sumă_actualăAici, INT_MIN reprezintă valoarea întreagă minimă.

Pas 2) La indicele 0, valoarea este 4. Deci, sumă_actuală = 0 + 4 = 4. Deoarece sumă_actuală este mai mare decât sumă_max, sumă_max devine 4.

Exemplu de algoritm Kadane pasul 2

Pas 3) La indicele 1, valoarea este -2. Deci, sumă_actuală = 4 + (-2) = 2.

De data asta sumă_actuală e mai puțin decât sumă_maxPrin urmare, valoarea sumă_max nu este actualizat.

Exemplu de algoritm Kadane pasul 3

Pas 4) Următoarea valoare este 1. Adăugând-o la sumă_actuală dă 3. Deoarece sumă_max (4) este totuși mai mare decât sumă_actuală, sumă_max nu este actualizat.

Exemplu de algoritm Kadane pasul 4

Pas 5) La indicele 3, valoarea este 3. Incrementare sumă_actuală cu 3 dăruiri sumă_actuală = 6.

Exemplu de algoritm Kadane pasul 5

În acest caz, sumă_max este mai mic decât sumă_actuală, asa de sumă_max este actualizat cu valoarea lui sumă_actuală.

Pas 6) Pentru ultimul element al tabloului, avem -1. Adăugându-l la sumă_actuală dă 5, care este mai mic decât sumă_max. Asa de, sumă_max rămâne 6.

Exemplu de algoritm Kadane pasul 6

Pe măsură ce am ajuns la sfârșitul matricei, algoritmul se termină aici. Acum, sumă_max conține suma maximă, care este 6. Subtabloul este {4, -2, 1, 3}.

Pseudo Code pentru algoritmul lui Kadane

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each element 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 -1,000,000,000
    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 pentru a calcula fiecare sumă posibilă a submatricei și pentru a o localiza pe cea mai mare. Este o abordare de tip forță brută; fiecare buclă rulează până la sfârșitul mulțime, dând O(N²) timp.

Algoritmul lui Kadane folosește o singură buclă, oferind O(N) timp și O(1) spațiu suplimentar. Pe o matrice de 100 de elemente, abordarea simplă efectuează 100 × 100 = 10,000 de operații, în timp ce algoritmul lui Kadane efectuează doar 100 - o creștere dramatică a vitezei pentru intrări mari.

Întrebări frecvente

Algoritmul lui Kadane stă la baza ingineriei de caracteristici ale inteligenței artificiale pentru date din serii temporale, detectarea ferestrelor de anomalii și partajarea recompenselor.ping în învățarea prin consolidare, helping Modelele identifică cel mai puternic interval de sumă pozitivă în semnalele zgomotoase.

Da. GitHub Copilot și GPT afișează în mod fiabil algoritmul lui Kadane în Python, C++ și Java, inclusiv variantele care returnează indicii de început și de sfârșit ai submatricei câștigătoare.

Algoritmul lui Kadane rulează în timp O(N) și spațiu auxiliar O(1) deoarece face o singură trecere tracregele doar o sumă curentă și o cea mai bună valoare de până acum.

Inițializează max_sum la primul element sau la infinit negativ în loc de zero. Algoritmul returnează apoi elementul cu cel mai mic negativ, care este răspunsul corect.

Utilizările comune sunt ferestrele de profit de cumpărare-vânzare de acțiuni, sumele la marginile imaginilor, intervalele de scorare genomică și analiza riscurilor financiare, unde cea mai bună fereastră de rentabilitate contiguă contează cel mai mult.

TracIndex de început temporar de fiecare dată când current_sum se resetează la elementul curent. Când max_sum se actualizează, capturează indicii de început și de sfârșit, astfel încât submatricea răspunsului să poată fi împărțită la sfârșit.

Metoda „împarte și cucerește” rezolvă submatricea maximă în O(N log N) prin combinarea sumelor la stânga, la dreapta și la încrucișări. Algoritmul lui Kadane este mai rapid la O(N) și mai ușor de codificat.

Da. Exemplul lui Kadane este un exemplu canonic de programare dinamică cu starea O(1), unde fiecare maxim nou care se termină la indicele i depinde de maximul care se termină la indicele i minus unu plus elementul curent.

Rezumați această postare cu: