Trovare il sottoarray di somma massima in JavaScript

In questa pagina, esploreremo dettagliatamente come individuare il sottoarray con la somma massima utilizzando JavaScript, fornendo spiegazioni chiare e presentando esempi pratici.

Iniziamo definendo un array di numeri su cui eseguire la ricerca del sottoarray con la somma massima:

// Definizione dell'array di numeri
var array = [-2, 1, -3, 4, -1, 2, 1, -5, 4];

Implementazione usando l’algoritmo di Kadane

L'algoritmo di Kadane è uno dei metodi più efficienti per individuare il sottoarray con la somma massima all'interno di un array. Si basa sull'idea di scorrere l'array una sola volta, mantenendo traccia della somma massima attuale e della somma corrente del sottoarray.

// Algoritmo di Kadane per individuare il sottoarray con la somma massima
var sommaMassimaAttuale = array[0];
var sommaSottoarray = array[0];

for (var i = 1; i < array.length; i++) {
  sommaSottoarray = Math.max(array[i], sommaSottoarray + array[i]);
  sommaMassimaAttuale = Math.max(sommaMassimaAttuale, sommaSottoarray);
}

In questo codice, iniziamo considerando il primo elemento come somma massima attuale e somma del sottoarray. Successivamente, attraverso un ciclo for, analizziamo gli elementi successivi dell'array. A ogni passaggio, confrontiamo la somma corrente del sottoarray con l'elemento corrente e scegliamo il massimo tra i due.

L'algoritmo di Kadane non fornisce direttamente il sottoarray, ma solo la somma massima. Possiamo estendere l'algoritmo per tracciare gli indici in modo da identificare i confini del sottoarray con la somma massima.

// Identificazione degli indici del sottoarray con la somma massima
var inizioSottoarray = 0;
var fineSottoarray = 0;
var tempSomma = 0;

for (var j = 0; j < array.length; j++) {
  tempSomma += array[j];

  if (tempSomma === sommaMassimaAttuale) {
    fineSottoarray = j;
    break;
  }

  if (tempSomma < 0) {
    tempSomma = 0;
    inizioSottoarray = j + 1;
  }
}

// Ottenere il sottoarray con la somma massima
var sottoarrayMassimo = array.slice(inizioSottoarray, fineSottoarray + 1);

In questo codice, utilizziamo un approccio lineare per identificare gli indici iniziali e finali del sottoarray con la somma massima. Iteriamo attraverso gli elementi e aggiorniamo gli indici in base alla somma corrente. Alla fine, otteniamo il sottoarray con la somma massima utilizzando slice().

Infine, possiamo stampare il sottoarray con la somma massima sulla console o presentarlo in modo più interattivo all'utente, a seconda del contesto dell'applicazione.

// Stampa del sottoarray con la somma massima sulla console
console.log("Il sottoarray con la somma massima è: " + sottoarrayMassimo); // Il sottoarray con la somma massima è: 4,-1,2,1

L'individuazione del sottoarray con la somma massima utilizzando l'algoritmo di Kadane è un approccio efficiente e ampiamente utilizzato. Questo processo coinvolge la gestione della somma corrente del sottoarray, mantenendo traccia della somma massima e degli indici per identificare il sottoarray desiderato.