Kadane (subarreglo de suma máxima)
Tema: Programación Dinámica · temarios: Syllabus OCI · Syllabus IOI
📍 Dónde se aprende: módulo 14 de la Ruta de Aprendizaje.
Qué hace
La suma máxima de un subarreglo contiguo no vacío, en una sola pasada. Es la DP más chica que existe: un estado, una decisión, sin tabla.
Complejidad: O(n) tiempo y O(1) memoria.
Cuándo usarlo
Cuando piden el mejor tramo contiguo: la racha más rentable, la mayor ganancia entre comprar y vender, el segmento de mejor promedio tras restarle el promedio. Solo tiene gracia si hay números negativos — con todos positivos la respuesta es el arreglo entero. Se aprende en el módulo 14 de la Ruta de Aprendizaje.
Implementación recomendada (C++)
// Suma máxima de un subarreglo NO VACÍO, y dónde está: [ini, fin] inclusive.
struct Tramo { long long suma; int ini, fin; };
Tramo kadane(const vector<int>& a) {
long long actual = a[0]; // mejor suma de un tramo que TERMINA aquí
int ini_actual = 0;
Tramo mejor = {a[0], 0, 0};
for (int i = 1; i < (int)a.size(); i++) {
if (actual < 0) { actual = a[i]; ini_actual = i; } // arrastrar resta: partir de nuevo
else actual += a[i]; // estirar el tramo que traía
if (actual > mejor.suma) mejor = {actual, ini_actual, i};
}
return mejor;
}⚠️ Notas
La regla if (actual < 0) es exactamente el max(a[i], actual + a[i]) del módulo 14: quedarse solo con a[i] conviene si y solo si lo que traías era negativo. Escrita con if puedes además llevar el índice de inicio, que es lo que pide la reconstrucción. ⚠️ Esta versión no admite el subarreglo vacío: con todos los valores negativos devuelve el mayor elemento, que es lo que piden casi todos los enunciados. Si el tuyo permite no elegir nada, la respuesta es max(0LL, kadane(a).suma) — léelo dos veces antes de enviar. Variantes: para el subarreglo de suma mínima, invierte los signos y vuelve a correrlo; para el circular, la respuesta es el máximo entre el Kadane normal y (suma total − Kadane del mínimo), con el caso aparte de que todos sean negativos. Si el enunciado agrega estados (“a lo más k borrados”, “dos tramos que no se tocan”), ya no es Kadane: es una DP con más de un valor por posición. La misma respuesta sale también con Sumas de prefijos (el máximo de pre[j] - min(pre[i])), y esa versión es la que se generaliza a 2D.