Problema di sottoarray massimo in Java

1. Panoramica

Il problema del subarray massimo è un'attività per trovare la serie di elementi contigui con la somma massima in un dato array.

Ad esempio, nell'array sottostante, il sottoarray evidenziato ha la somma massima (6):

In questo tutorial, daremo un'occhiata a due soluzioni per trovare il sottoarray massimo in un array . Uno dei quali progetteremo con O (n) complessità temporale e spaziale.

2. Algoritmo di forza bruta

La forza bruta è un approccio iterativo per risolvere un problema. Nella maggior parte dei casi, la soluzione richiede una serie di iterazioni su una struttura dati. Nelle prossime sezioni, applicheremo questo approccio per risolvere il problema del subarray massimo.

2.1. Approccio

In generale, la prima soluzione che viene in mente è calcolare la somma di ogni possibile sottoarray e restituire quello con la somma massima.

Per cominciare, calcoleremo la somma di ogni sottoarray che inizia dall'indice 0. Allo stesso modo, troveremo tutti i sottoarray a partire da ogni indice da 0 a n-1 dove n è la lunghezza dell'array:

Quindi inizieremo dall'indice 0 e aggiungeremo ogni elemento alla somma corrente nell'iterazione. Terremo anche traccia della somma massima vista finora . Questa iterazione è mostrata sul lato sinistro dell'immagine sopra.

Sul lato destro dell'immagine, possiamo vedere l'iterazione che inizia dall'indice 3 . Nell'ultima parte di questa immagine, abbiamo il sottoarray con la somma massima tra l'indice 3 e 6 .

Tuttavia, il nostro algoritmo continuerà a trovare tutti i sottoarray a partire da indici compresi tra 0 e n-1 .

2.2. Implementazione

Vediamo ora come possiamo implementare questa soluzione in Java:

public int maxSubArray(int[] nums) { int n = nums.length; int maximumSubArraySum = Integer.MIN_VALUE; int start = 0; int end = 0; for (int left = 0; left < n; left++) { int runningWindowSum = 0; for (int right = left; right  maximumSubArraySum) { maximumSubArraySum = runningWindowSum; start = left; end = right; } } } logger.info("Found Maximum Subarray between {} and {}", start, end); return maximumSubArraySum; }

Come previsto, aggiorniamo il valore maximumSubArraySum se la somma corrente è maggiore della somma massima precedente. In particolare, aggiorniamo anche l' inizio e la fine per scoprire le posizioni dell'indice di questo sottoarray .

2.3. Complessità

In generale, la soluzione della forza bruta itera sull'array molte volte per ottenere ogni soluzione possibile. Ciò significa che il tempo impiegato da questa soluzione cresce in modo quadratico con il numero di elementi nell'array. Questo potrebbe non essere un problema per array di piccole dimensioni. Ma man mano che la dimensione dell'array cresce, questa soluzione non è efficiente.

Ispezionando il codice, possiamo anche vedere che ci sono due cicli for annidati . Pertanto, possiamo concludere che la complessità temporale di questo algoritmo è O (n2) .

Nelle sezioni successive, risolveremo questo problema in complessità O (n) utilizzando la programmazione dinamica.

3. Programmazione dinamica

La programmazione dinamica risolve un problema dividendolo in sottoproblemi più piccoli. Questo è molto simile alla tecnica di risoluzione dell'algoritmo divide et impera. La differenza principale, tuttavia, è che la programmazione dinamica risolve un sottoproblema solo una volta.

Memorizza quindi il risultato di questo sottoproblema e successivamente lo riutilizza per risolvere altri sottoproblemi correlati. Questo processo è noto come memoizzazione .

3.1. Algoritmo di Kadane

L'algoritmo di Kadane è una soluzione popolare al problema del subarray massimo e questa soluzione si basa sulla programmazione dinamica.

La sfida più importante nella risoluzione di un problema di programmazione dinamica è trovare i sottoproblemi ottimali .

3.2. Approccio

Comprendiamo questo problema in modo diverso:

Nell'immagine sopra, assumiamo che il sottoarray massimo termini nell'ultima posizione dell'indice. Pertanto, la somma massima di subarray sarà:

maximumSubArraySum = max_so_far + arr[n-1]

max_so_far è la somma massima di un sottoarray che termina con l'indice n-2 . Questo è mostrato anche nell'immagine sopra.

Ora possiamo applicare questa ipotesi a qualsiasi indice dell'array. Ad esempio, la somma massima del sottoarray che termina con n-2 può essere calcolata come:

maximumSubArraySum[n-2] = max_so_far[n-3] + arr[n-2]

Pertanto, possiamo concludere che:

maximumSubArraySum[i] = maximumSubArraySum[i-1] + arr[i]

Ora, poiché ogni elemento dell'array è uno speciale sottoarray di dimensione uno, dobbiamo anche controllare se un elemento è maggiore della somma massima stessa:

maximumSubArraySum[i] = Max(arr[i], maximumSubArraySum[i-1] + arr[i])

Osservando queste equazioni, possiamo vedere che abbiamo bisogno di trovare la somma massima di sottoarray in ogni indice dell'array. Quindi, abbiamo diviso il nostro problema in n sottoproblemi. Possiamo trovare la somma massima in ogni indice iterando l'array solo una volta:

L'elemento evidenziato mostra l'elemento corrente nell'iterazione. Ad ogni indice, applicheremo l'equazione derivata in precedenza per calcolare un valore per max_ending_here . Questo ci aiuta a identificare se dobbiamo includere l'elemento corrente nel sottoarray o iniziare un nuovo sottoarray a partire da questo indice .

Another variable, max_so_far is used to store the maximum subarray sum found during the iteration. Once we iterate over the last index, max_so_far will store the sum of the maximum subarray.

3.3. Implementation

Again, let's see how we can now implement the Kadane algorithm in Java, following the above approach:

public int maxSubArraySum(int[] arr) {       int size = arr.length;     int start = 0;     int end = 0;       int maxSoFar = 0, maxEndingHere = 0;       for (int i = 0; i  maxEndingHere + arr[i]) {             start = i;             maxEndingHere = arr[i];         } else             maxEndingHere = maxEndingHere + arr[i];           if (maxSoFar < maxEndingHere) {             maxSoFar = maxEndingHere;             end = i;         }     } logger.info("Found Maximum Subarray between {} and {}", start, end);     return maxSoFar; }

Here, we updated the start and end to find the maximum subarray indices.

3.4. Complexity

Since we only need to iterate the array once, the time complexity of this algorithm is O(n).

So as we can see, the time taken by this solution grows linearly with the number of elements in the array. Consequently, it is more efficient than the brute force approach we discussed in the last section.

4. Conclusion

In questo breve tutorial, abbiamo descritto due modi per risolvere il problema del subarray massimo.

Per prima cosa, abbiamo esplorato un approccio di forza bruta e abbiamo visto che questa soluzione iterativa si traduceva in tempo quadratico. Successivamente, abbiamo discusso l'algoritmo di Kadane e utilizzato la programmazione dinamica per risolvere il problema in tempo lineare.

Come sempre, il codice sorgente completo dell'articolo è disponibile su GitHub.