Maximum Subarray

Un sottoarray è una sequenza di elementi adiacenti di una lista, senza interruzioni. Tra tutti i sottoarray non vuoti di una lista di interi, vuoi quello i cui elementi hanno la somma più alta e restituisci tale somma.

In [2, -4, 3, -1, 5, -6, 1] la sequenza migliore è [3, -1, 5], con una somma pari a 7. Include -1 perché il 5 che lo segue compensa più che ampiamente il suo valore negativo, ed esclude il 2 iniziale perché il -4 che lo segue costa più di quanto il 2 apporti.

La classica soluzione in un'unica passata è l'algoritmo di Kadane. Scorri la lista e tieni traccia della somma migliore di una sequenza che termina nell'elemento corrente. Per ogni elemento ci sono solo due possibilità: estendere la sequenza che terminava nell'elemento precedente oppure ricominciare con una nuova sequenza che inizia qui. Estendere conviene solo finché la sequenza precedente ha una somma positiva; quando quella somma scende a zero o al di sotto, mantenerla può solo essere uno svantaggio, quindi si riparte da zero. La risposta è la somma più alta tra quelle delle sequenze incontrate lungo il percorso.

Per l'esempio, le somme migliori delle sequenze che terminano in ciascuna posizione sono 2, -2, 3, 2, 7, 1 e 2, quindi la risposta è 7. Ogni elemento viene esaminato una volta sola, perciò il lavoro cresce linearmente con la lunghezza della lista.

Scrivi una funzione chiamata maxSubArray che riceve un elenco di numeri interi nums e restituisce la somma più grande di un sottoarray contiguo e non vuoto di nums.

Vincoli: 1 ≤ nums.length ≤ 10^5, -10^4 ≤ nums[i] ≤ 10^4.