Maximum Subarray

Um subarray é uma sequência de elementos vizinhos de uma lista, sem lacunas. Entre todos os subarrays não vazios de uma lista de inteiros, você quer aquele cujos elementos somam o maior valor, e retorna essa soma.

Em [2, -4, 3, -1, 5, -6, 1], a melhor sequência é [3, -1, 5], com soma 7. Ela mantém o -1 porque o 5 que vem depois compensa mais do que o suficiente, e deixa de fora o 2 do início porque o -4 que vem em seguida custa mais do que o 2 acrescenta.

A solução clássica de passagem única é o algoritmo de Kadane. Percorra a lista e mantenha a maior soma de uma sequência que termina no elemento atual. Em cada elemento, há apenas duas opções: estender a sequência que terminou no elemento anterior ou recomeçar com uma nova sequência que começa aqui. Estender só compensa enquanto a sequência anterior tem uma soma positiva; quando essa soma chega a zero ou fica abaixo dele, carregá-la adiante só pode prejudicar, então você começa do zero. A resposta é a maior soma de sequência encontrada ao longo do percurso.

No exemplo, as melhores somas de sequências que terminam em cada posição são 2, -2, 3, 2, 7, 1 e 2, então a resposta é 7. Cada elemento é examinado uma vez, portanto o trabalho cresce linearmente com o comprimento da lista.

Escreva uma função chamada maxSubArray que recebe uma lista de números inteiros nums e retorna a maior soma de um subarray contíguo e não vazio de nums.

Restrições: 1 ≤ nums.length ≤ 10^5, -10^4 ≤ nums[i] ≤ 10^4.