¿Cómo obtienes la suma máxima de un subarray en O(n)?

Algoritmo de Kadane

La idea de Kadane: recorre el array guardando cur, la mejor suma de un subarray que termina en la posición actual.

En cada número x, amplía el subarray anterior (cur + x) o empieza de nuevo en x, lo que sea mayor. Guarda el mejor cur visto.

Una pasada, O(n) de tiempo, O(1) de memoria.

def max_subarray(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

Kadane: ampliar o reiniciar en cada elemento.