Medio–difícil · una pasada, una idea
Suma máxima de subarray
De todos los tramos contiguos del array, ¿cuál tiene la suma más grande? La fuerza bruta es O(n²). La idea clave cabe en una frase.
En una fraseAlgoritmo de Kadane: running = max(a[i], running + a[i]) y best = max(best, running); sigue siendo correcto con arrays todo negativos porque el tramo debe ser no vacío.
El problema
Entrada: La primera línea es un entero n (1 ≤ n ≤ 1000). La segunda línea contiene n enteros separados por espacios (−1000 ≤ ai ≤ 1000). Los números pueden ser negativos.
Salida: La mayor suma posible de un tramo contiguo no vacío.
Ejemplos:
| Entrada | Salida |
|---|---|
8 | 6 |
5 | -1 |
1 | 5 |
En el primer ejemplo el mejor tramo es 4 -1 2 1 = 6. En el segundo todos los números son negativos, pero aun así hay que elegir uno: la respuesta es −1, no 0. Ahí es donde fallan casi todas las soluciones.
Tu solución
Entrada personalizada para «Ejecutar mi entrada»
La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.
¿Atascado? Pistas
Pista 1 — Primero la fuerza bruta, para notar el desperdicio
Prueba cada inicio i y cada final j, suma el rango y quédate con el máximo. Eso es O(n²): para n = 1000 son alrededor de un millón de sumas, y la mayoría recalculan sumas que ya tenías. La solución rápida nunca mira hacia atrás.
Pista 2 — Basta con un acumulador
Mantén cur = la mejor suma de un tramo que termina en la posición actual. Cuando llega el siguiente número x tienes exactamente dos opciones: extender el tramo (cur + x) o empezar uno nuevo en x. Toma la mayor. Luego actualiza best si cur lo superó.
Pista 3 — La idea de una frase
Si cur es negativo, solo puede arrastrar hacia abajo al siguiente número: tíralo y empieza de cero. Eso es todo: if (cur < 0) cur = x; else cur = cur + x;. Lo demás es contabilidad.
Solución (¡inténtalo primero!)
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int best, cur;
cin >> best;
cur = best;
for (int i = 1; i < n; i++) {
int x;
cin >> x;
if (cur < 0) cur = x;
else cur = cur + x;
if (cur > best) best = cur;
}
cout << best << endl;
return 0;
}Este es el algoritmo de Kadane, y es la introducción estándar a la programación dinámica: cur es un estado que resume en un solo número todo lo que necesitas saber del pasado. No recordaste el array: recordaste lo único que importa. Esa reformulación, "¿cuál es el mínimo que debo arrastrar?", es toda la disciplina. Y es el último problema de la cadena: ya has cubierto entrada, bucles, arrays, cadenas, bits, ordenación, búsqueda y un algoritmo de verdad. Vuelve a la lista y mira cuántos puedes hacer sin pistas.
Análisis profundo
Por qué funciona
Mantén cur = la mejor suma de un tramo que termina justo aquí. Cuando llega el siguiente número tienes dos opciones: extender el tramo o empezar uno nuevo en él. Toma la mayor.
El coste
O(n) en una pasada con dos variables extra. Enumerar todos los rangos es O(n²), y la mayoría de esas sumas recalculan lo que ya tenías.
Dónde falla
- Empezar
besten 0 imprime 0 con entradas todas negativas, pero el tramo vacío no está permitido: la respuesta es el mayor número negativo. - Decidir con
if (x > 0)en vez deif (cur < 0)extiende un acumulado negativo que debías abandonar, y el máximo sale demasiado bajo.
Siguiente paso
Aquí termina la cadena. Mira el primer problema: has llegado muy lejos.
Dos cosas para recordar
- Un acumulado negativo solo te arrastra: tíralo y reinicia en el número actual.
- La pregunta central de la programación dinámica: ¿cuál es lo mínimo que debo arrastrar?
🐞 Esta versión falla: ábrela y pruébala
best empieza en 0: con entradas negativas da 0, pero el tramo vacío no vale
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int best = 0, cur = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (cur < 0) cur = x;
else cur = cur + x;
if (cur > best) best = cur;
}
cout << best << endl;
return 0;
}