Introducción a la Programación Dinámica Lineal

La programación dinámica (DP) lineal se caracteriza por tener una estructura de transición de estados que sigue un orden secuencial claro, generalmente sobre estructuras de datos como arreglos unidimensionales o bidimensionales, colas o pilas. A diferencia de la DP en árboles o gráficos complejos, la dependencia de los estados se puede procesar de forma lineal.

1. Subsecuencia Creciente Más Larga (LIS)

El problema del LIS busca encontrar la longitud de la subserie más larga de un arreglo donde los elementos están en orden estrictamente creciente. Existen variantes como la subserie no decreciente, decreciente o no creciente.

Optimización $O(n \log n)$

Definimos un arreglo auxiliar cola donde cola[i] almacena el valor mínimo posible del último elemento de una subsecuencia de longitud i. Este arreglo siempre se mantendrá ordenado de forma monótona, lo que permite el uso de búsqueda binaria.

• Si el elemento actual es mayor que el último en cola, se añade al final.
• De lo contrario, se busca mediante búsqueda binaria el primer elemento en cola que sea mayor o igual al actual y se reemplaza.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int calcular_lis(const vector<int>& datos) {
    if (datos.empty()) return 0;
    vector<int> tails;
    for (int x : datos) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }
    return tails.size();
}

Para variaciones como la subsecuencia no decreciente, se debe utilizar upper_bound en lugar de lower_bound.

2. Suma Máxima de un Subsegmento Continuo

Este modelo busca el subarreglo cuya suma sea la mayor posible. La idea central es decidir si extender el segmento actual o comenzar uno nuevo desde la posición presente.

Si suma_actual + valor[i] < valor[i], es preferible descartar el acumulado anterior y reiniciar el conteo. La complejidad es $O(n)$ y solo requiere espacio constante si se procesa en línea.

Extensión: Longitud mínima $k$

Cuando se requiere que el subarreglo tenga al menos $k$ elementos, podemos utilizar sumas de prefijos. Definimos S[i] como la suma de los primeros i elementos. La suma de un rango [i-k+1, i] es S[i] - S[i-k]. Para optimizar, mantenemos el valor mínimo de S[j] donde $j \leq i-k$.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long suma_maxima_k(const vector<int>& v, int k) {
    int n = v.size();
    vector<long long> pref(n + 1, 0);
    for (int i = 0; i < n; ++i) pref[i+1] = pref[i] + v[i];

    long long mejor_global = -2e18; // Valor muy pequeño
    long long min_pref = 0;

    for (int i = k; i <= n; ++i) {
        min_pref = min(min_pref, pref[i - k]);
        mejor_global = max(mejor_global, pref[i] - min_pref);
    }
    return mejor_global;
}

3. Subsecuencia Común Más Larga (LCS)

Dadas dos secuencias $A$ y $B$, el objetivo es hallar la longitud de la subsecuencia más larga presente en ambas. El estado estándar es dp[i][j], que representa la LCS de los prefijos $A[1 \dots i]$ y $B[1 \dots j]$.

La relación de recurrencia es:

• Si $A[i] = B[j]$: dp[i][j] = dp[i-1][j-1] + 1
• Si $A[i] \neq B[j]$: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Reconstrucción del camino

Para obtener la cadena resultante, se puede retroceder desde dp[n][m]. Si los caracteres coinciden, se incluyen en el resultado y se mueve diagonalmente; de lo contrario, se mueve hacia la celda con el valor máximo (arriba o izquierda).

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

string obtener_lcs(string s1, string s2) {
    int n = s1.size(), m = s2.size();
    vector<vector<int>> matriz(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s1[i - 1] == s2[j - 1]) matriz[i][j] = matriz[i - 1][j - 1] + 1;
            else matriz[i][j] = max(matriz[i - 1][j], matriz[i][j - 1]);
        }
    }

    string res = "";
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (s1[i - 1] == s2[j - 1]) {
            res += s1[i - 1];
            i--; j--;
        } else if (matriz[i - 1][j] > matriz[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    reverse(res.begin(), res.end());
    return res;
}

Optimización mediante Autómata de Secuencias

Cuando una de las cadenas es muy larga ($n$) y la otra corta ($m$), o el alfabeto $\Sigma$ es limitado, podemos mejorar el tiempo de búsqueda. Preprocesando un arreglo siguiente[i][caracter] que indique la primera aparición del caracter después de la posición i, podemos reducir la complejidad a $O(m^2 + n|\Sigma|)$.

// Estructura conceptual del siguiente salto
int nxt[MAXN][ALFABETO];
void preprocesar(const string& s) {
    int n = s.size();
    for (int c = 0; c < 26; ++c) nxt[n + 1][c] = n + 1;
    for (int i = n; i >= 1; --i) {
        for (int c = 0; c < 26; ++c) nxt[i][c] = nxt[i + 1][c];
        nxt[i][s[i-1] - 'a'] = i;
    }
}

4. Suma Máxima de Subsecuancia Creciente

Este problema combina LIS con la suma de los valores. dp[i] representa la suma máxima de una subsecuencia creciente que termina en el índice i.

La transición es: dp[i] = valor[i] + max({dp[j]}) para todo $j < i$ tal que valor[j] < valor[i]. Aunque la implementación básica es $O(n^2)$, se puede optimizar a $O(n \log n)$ utilizando estructuras de datos como Árboles de Fenwick o Segment Trees sobre el dominio de los valores.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long max_suma_creciente(const vector<int>& arr) {
    int n = arr.size();
    vector<long long> dp(n);
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        dp[i] = arr[i];
        for (int j = 0; j < i; ++j) {
            if (arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + arr[i]);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}