Algoritmo di Kadence: sottoarray contiguo a somma più grande

Qual è la somma massima di un sottoarray contiguo?

Un sottoarray è una parte continua di un array. Può essere un singolo elemento di un array o una frazione dell'array. Il sottoarray contiguo con la somma più grande indica un sottoarray che ha il valore della somma massima.

Ad esempio, si consideri l'array {-10, 5, 1, 6, -9, 2, -7, 3, -5}. I suoi sottoarray possono essere {-10, 5, 1, 6}, {5, 1, 6}, oppure {2, -7, 3, -5}, e così via. Tuttavia, {5, 1, 6, 3} non può essere un sottoarray perché gli elementi non sono in sequenza contigua.

Come potete notare, tra tutti i sottoarray, quello evidenziato {5, 1, 6} ha il valore di somma massimo:

La somma della sotto-matrice {5, 1, 6} è 12, la somma massima tra tutte le possibili sotto-matrici della matrice sopra riportata. Pertanto, per questa matrice, la sotto-matrice contigua con somma massima è {5, 1, 6}.

Un approccio semplice per risolvere il problema della somma massima in sottoarray contigui

Il modo più semplice per risolvere questo problema è utilizzare due cicli per trovare tutti i sottoarray, calcolare la somma e quindi trovare il suo valore massimo.

Ecco il diagramma di flusso per il metodo semplice per trovare la sotto-matrice contigua con la somma maggiore. Si tratta di un approccio di forza bruta, in quanto si esaminano tutte le possibili sotto-matrici.

Ecco i semplici passaggi per farlo.

Passo 1) Inizializzare somma massima con il valore intero minimo e impostato iniziare and fine a zero.

Passo 2) lasciare i and j siano gli indici dell'array dove j è più grande di O uguale a i; i segna l'inizio del sottoarray e j la sua fine.

Passo 3) somma_attuale contiene la somma progressiva. Dopo ogni aggiornamento, controlla se somma_attuale è maggiore somma massima.

Passo 4) If somma_attuale è maggiore, sostituire somma massima con esso.

Passo 5) Quando j raggiunge la fine dell'array, incrementa i e ripristina somma_attuale a 0.

Passo 6) Ripeti fino al i raggiunge la fine dell'array. somma massima quindi detiene la somma del sottoarray più grande.

Soprannome Code per un approccio semplice

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

C++ Attuazione dell'approccio semplice

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

Produzione:

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

Python Attuazione dell'approccio semplice

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)

Produzione:

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

Algoritmo di Kadane per trovare la sotto-matrice contigua con la somma maggiore

L'algoritmo di Kadane è un metodo di programmazione dinamica che utilizza un singolo ciclo anziché due. Gestisce array con numeri misti positivi e negativi, purché almeno un valore sia non negativo.

Per trovare la sotto-matrice contigua con la somma maggiore, ci bastano due variabili. Ecco il diagramma di flusso:

Ecco i passaggi per l'algoritmo di Kadane:

Passo 1) Crea due variabili, somma_attuale and somma massima.

somma_attuale mantiene la somma massima che termina in uno specifico indice dell'array, mentre somma massima memorizza il valore di somma più alto osservato finora.

Passo 2) Aggiungi ogni elemento dell'array a somma_attualeQuindi, verifica le due condizioni seguenti:

• If somma_attuale è minore dell'elemento corrente, quindi somma_attuale diventa l'elemento corrente.
• If somma massima è meno di somma_attuale, poi somma massima diventa somma_attuale.

Passo 3) Dopo aver ripetuto il passaggio precedente per l'intero array, somma massima detiene la somma più grande del sottoarray contiguo.

Esempio dell'algoritmo di Kadane

Dimostriamo l'algoritmo di Kadane su un array di piccole dimensioni e analizziamo passo passo ogni fase del processo per trovare il sottoarray contiguo con la somma maggiore.

Supponiamo che l'array dato sia del tipo seguente:

Ecco i passaggi dell'algoritmo di Kadane:

Passo 1) Crea due variabili, somma_attuale and somma massima. Assegna INT_MIN a somma massima e da zero a somma_attualeQui, INT_MIN rappresenta il valore intero minimo.

Passo 2) All'indice 0, il valore è 4. Quindi, somma_attuale = 0 + 4 = 4. Poiché somma_attuale è più grande di somma massima, somma massima diventa 4.

Passo 3) All'indice 1, il valore è -2. Quindi, somma_attuale = 4 + (-2) = 2.

Stavolta somma_attuale è meno di somma massima. Di conseguenza, il valore di somma massima non è aggiornato.

Passo 4) Il valore successivo è 1. Aggiungendolo a somma_attuale dà 3. Poiché somma massima (4) è ancora maggiore di somma_attuale, somma massima non è aggiornato.

Passo 5) All'indice 3, il valore è 3. Incremento somma_attuale da 3 dà somma_attuale = 6.

In questo caso, somma massima è più piccolo di somma_attuale, Così somma massima viene aggiornato con il valore di somma_attuale.

Passo 6) Per l'ultimo elemento dell'array, abbiamo -1. Aggiungendolo a somma_attuale dà 5, che è più piccolo di somma massima. Così, somma massima rimane 6.

Poiché abbiamo raggiunto la fine dell'array, l'algoritmo termina qui. Ora, somma massima contiene la somma massima, che è 6. La sotto-matrice è {4, -2, 1, 3}.

Soprannome Code per l'algoritmo di 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++ Implementazione dell'algoritmo di 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]));
}

Produzione:

largest sum is 12

Python Implementazione dell'algoritmo di 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])

Produzione:

largest sum is 12

Analisi della complessità per il sottoarray contiguo della somma più grande

L'approccio semplice utilizza due cicli per calcolare ogni possibile somma di sottoarray e individuare quella più grande. È un approccio di forza bruta; ogni ciclo viene eseguito fino alla fine del schieramento, Dando O(N²) tempo.

L'algoritmo di Kadane utilizza un solo ciclo, offrendo un tempo O(N) e uno spazio aggiuntivo O(1). Su un array di 100 elementi, l'approccio semplice esegue 100 × 100 = 10,000 operazioni, mentre quello di Kadane ne esegue solo 100, un notevole incremento di velocità per input di grandi dimensioni.

DOMANDE FREQUENTI