Maximum Subarray

Un subarreglo es una secuencia de elementos vecinos de una lista, tomada sin saltos. Entre todos los subarreglos no vacíos de una lista de enteros, quieres el que tenga la suma más alta de sus elementos y devuelves esa suma.

En [2, -4, 3, -1, 5, -6, 1], la mejor secuencia es [3, -1, 5], con una suma de 7. Conserva el -1 porque el 5 que viene después compensa con creces su valor, y excluye el 2 del principio porque el -4 que le sigue cuesta más de lo que aporta el 2.

La solución clásica de una sola pasada es el algoritmo de Kadane. Recorre la lista y lleva la cuenta de la mayor suma de una secuencia que termina en el elemento actual. En cada elemento solo hay dos opciones: extender la secuencia que terminaba en el elemento anterior, o empezar de nuevo con una nueva secuencia que comienza aquí. Extender solo resulta ventajoso mientras la secuencia anterior tenga una suma positiva; una vez que esa suma llega a cero o es negativa, mantenerla solo puede perjudicar, así que empiezas de nuevo. La respuesta es la mayor suma de secuencia que se haya visto durante el recorrido.

Para el ejemplo, las mejores sumas de secuencias que terminan en cada posición son 2, -2, 3, 2, 7, 1 y 2, así que la respuesta es 7. Cada elemento se examina una vez, por lo que el trabajo crece linealmente con la longitud de la lista.

Escribe una función llamada maxSubArray que reciba una lista de enteros nums y devuelva la suma más grande de un subarreglo contiguo y no vacío de nums.

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