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.

🔗 Relacionados