Problema hermoso: subarreglo de máxima suma en O(n)

Encontrar el subarreglo de máxima suma es un problema clásico. En este episodio vamos a hablar de 4 soluciones diferentes:

Solución ingenua en O(n^2);
Solución usando divide y vencerás en O(n log n);
Solución usando programación dinámica en O(n);
Y la más bonita de todas: solución en O(n) usando ninguna técnica en particular, solamente una observación muy inteligente de las que dices "¿Cómo no pensé en eso?" cuando te la explican...

Puedes usar Codeo para probar tu código y verificar si tu solución está correcta: https://codeo.app/problemas/0x94-suba...

Es mucho mejor verlo en vivo porque puedes hacerme preguntas en el chat (me encanta responder).

======================

¿Qué es Codeo?

Codeo es una plataforma para practicar algoritmos y estructuras de datos que estoy desarrollando en mi tiempo libre. Codeo te da problemas, tu escribes el código y Codeo lo ejecuta y te dice si está correcto.

https://codeo.app