Subsecuencias crecientes secuenciales de K más largas

¿Por qué creé un hilo duplicado?

Creé este hilo después de leer La subsecuencia creciente más larga con K excepciones permitidas . Me di cuenta de que la persona que hacía la pregunta no había entendido realmente el problema, porque se refería a un enlace que resuelve el problema "Subarreglo de mayor aumento con un cambio permitido". Entonces, las respuestas que obtuvo fueron irrelevantes para el problema de LIS.

Descripción del problema

Supongamos que una matriz A se da con longitud N . Encuentre la subsecuencia creciente más larga con K excepciones permitidas.

Ejemplo
1) N = 9, K = 1

A = [3,9,4,5,8,6,1,3,7]

Respuesta: 7

Explicación:

La subsecuencia creciente más larga es: 3,4,5,8 (o 6), 1 (excepción), 3,7 -> total = 7

2) N = 11, K = 2

A = [5,6,4,7,3,9,2,5,1,8,7]

respuesta: 8

Lo que he hecho hasta ahora ...

Si K = 1, solo se permite una excepción. Si se usa el algoritmo conocido para calcular la subsecuencia de mayor aumento en O (NlogN) ( haga clic aquí para ver este algoritmo ), entonces podemos calcular el LIS a partir de A [0] a A [N-1] para cada elemento de la matriz R. guardar los resultados en una nueva matriz de L con un tamaño de N . Mirando el ejemplo n.1, la matriz L sería: L = [1,2,2,3,4,4,4,4,5].

Usando la lógica inversa, calculamos la matriz R , cada elemento del cual contiene la secuencia decreciente más larga actual de N-1 a 0.

El LIS con una excepción es solo sol = max (sol, L [i] + R [i + 1]), donde sol se inicializa como sol = L [N-1] . Entonces calculamos LIS desde 0 hasta un índice i (excepción), luego paramos e iniciamos un nuevo LIS hasta N-1 .

A=[3,9,4,5,8,6,1,3,7]

L=[1,2,2,3,4,4,4,4,5]

R=[5,4,4,3,3,3,3,2,1]

Sol = 7

-> explicación paso a paso:

init: sol = L[N]= 5

i=0 : sol = max(sol,1+4) = 5 
i=1 : sol = max(sol,2+4) = 6
i=2 : sol = max(sol,2+3) = 6
i=3 : sol = max(sol,3+3) = 6
i=4 : sol = max(sol,4+3) = 7
i=4 : sol = max(sol,4+3) = 7
i=4 : sol = max(sol,4+2) = 7
i=5 : sol = max(sol,4+1) = 7

Complejidad: O (NlogN + NlogN + N) = O (NlogN)

porque las matrices R, L necesitan tiempo NlogN para calcular y también necesitamos Θ (N) para encontrar sol .

Código para k = 1 problema

#include <stdio.h>
#include <vector>

std::vector<int> ends;

int index_search(int value, int asc) {
    int l = -1;
    int r = ends.size() - 1;
    while (r - l > 1) { 
        int m = (r + l) / 2; 
        if (asc && ends[m] >= value) 
            r = m; 
        else if (asc && ends[m] < value)
            l = m;
        else if (!asc && ends[m] <= value)
            r = m;
        else
            l = m;
    } 
    return r;
}

int main(void) {
    int n, *S, *A, *B, i, length, idx, max;

    scanf("%d",&n);
    S = new int[n];
    L = new int[n];
    R = new int[n];
    for (i=0; i<n; i++) {
        scanf("%d",&S[i]);
    }

    ends.push_back(S[0]);
    length = 1;
    L[0] = length;
    for (i=1; i<n; i++) {
        if (S[i] < ends[0]) {
            ends[0] = S[i];
        }
        else if (S[i] > ends[length-1]) {
            length++;
            ends.push_back(S[i]);
        }
        else {
            idx = index_search(S[i],1);
            ends[idx] = S[i];
        }
        L[i] = length;
    }

    ends.clear();
    ends.push_back(S[n-1]);
    length = 1;
    R[n-1] = length;
    for (i=n-2; i>=0; i--) {
        if (S[i] > ends[0]) {
            ends[0] = S[i];
        }
        else if (S[i] < ends[length-1]) {
            length++;
            ends.push_back(S[i]);
        }
        else {
            idx = index_search(S[i],0);
            ends[idx] = S[i];
        }
        R[i] = length;
    }

    max = A[n-1];
    for (i=0; i<n-1; i++) {
        max = std::max(max,(L[i]+R[i+1]));
    }

    printf("%d\n",max);
    return 0;
}

Generalización a K excepciones

He proporcionado un algoritmo para K = 1. No tengo idea de cómo cambiar el algoritmo anterior para que funcione con K excepciones. Me alegraría si alguien pudiera ayudarme.

( PS. Si es necesario, puedo proporcionar código para el algoritmo K = 1 en C ++.)

Esta respuesta se modifica de mi respuesta a una pregunta similar en Computer Science Stackexchange.

El problema LIS con, a lo sumo, k excepciones admite un algoritmo O (n log² n) que utiliza la relajación lagrangiana. Cuando k es mayor que log n, esto mejora asintóticamente en el O (nk log n) DP, que también explicaremos brevemente.

Supongamos que DP [a] [b] denota la longitud de la subsecuencia creciente más larga con, como máximo, excepciones b (posiciones en las que el entero anterior es mayor que el siguiente) que termina en el elemento b a. Este DP no está involucrado en el algoritmo, pero definirlo facilita la prueba del algoritmo.

Por conveniencia, asumiremos que todos los elementos son distintos y que el último elemento de la matriz es su máximo. Tenga en cuenta que esto no nos limita, ya que solo podemos agregar m / 2n a la enésima apariencia de cada número, y agregar infinito a la matriz y restar uno de la respuesta. Sea V la permutación para la cual 1 <= V [i] <= n es el valor del i-ésimo elemento.

Para resolver el problema en O (nk log n), mantenemos la constante de que DP [a] [b] se ha calculado para b <j. Bucle j de 0 a k, en la iteración j calculando DP [a] [j] para todo a. Para hacer esto, repita i de 1 a n. Mantenemos el máximo de DP [x] [j-1] sobre x <i y una estructura de datos máxima de prefijo que en el índice i tendrá DP [x] [j] en la posición V [x] para x <i, y 0 en cualquier otra posición.

Tenemos DP [i] [j] = 1 + max (DP [i '] [j], DP [x] [j-1]) donde vamos sobre i', x <i, V [i '] < V [i]. El prefijo máximo de DP [x] [j-1] nos da el máximo de términos del segundo tipo, y la consulta de la estructura de datos máxima de prefijo para el prefijo [0, V [i]] nos da el máximo de términos del primer tipo. Luego actualice la estructura de datos de prefijo máximo y prefijo máximo.

Aquí hay una implementación en C ++ del algoritmo. Tenga en cuenta que esta implementación no asume que el último elemento de la matriz es su máximo, o que la matriz no contiene duplicados.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Fenwick tree for prefix maximum queries
class Fenwick {
    private:
        vector<int> val;
    public:
        Fenwick(int n) : val(n+1, 0) {}

        // Sets value at position i to maximum of its current value and 
        void inc(int i, int v) {
            for (++i; i < val.size(); i += i & -i) val[i] = max(val[i], v);
        }

        // Calculates prefix maximum up to index i
        int get(int i) {
            int res = 0;
            for (++i; i > 0; i -= i & -i) res = max(res, val[i]);
            return res;
        }
};

// Binary searches index of v from sorted vector
int bins(const vector<int>& vec, int v) {
    int low = 0;
    int high = (int)vec.size() - 1;
    while(low != high) {
        int mid = (low + high) / 2;
        if (vec[mid] < v) low = mid + 1;
        else high = mid;
    }
    return low;
}

// Compresses the range of values to [0, m), and returns m
int compress(vector<int>& vec) {
    vector<int> ord = vec;
    sort(ord.begin(), ord.end());
    ord.erase(unique(ord.begin(), ord.end()), ord.end());
    for (int& v : vec) v = bins(ord, v);
    return ord.size();
}

// Returns length of longest strictly increasing subsequence with at most k exceptions
int lisExc(int k, vector<int> vec) {
    int n = vec.size();
    int m = compress(vec);
    vector<int> dp(n, 0);
    for (int j = 0;; ++j) {
        Fenwick fenw(m+1); // longest subsequence with at most j exceptions ending at this value
        int max_exc = 0; // longest subsequence with at most j-1 exceptions ending before this
        for (int i = 0; i < n; ++i) {
            int off = 1 + max(max_exc, fenw.get(vec[i]));
            max_exc = max(max_exc, dp[i]);

            dp[i] = off;
            fenw.inc(vec[i]+1, off);
        }
        if (j == k) return fenw.get(m);
    }
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> vec(n);
    for (int i = 0; i < n; ++i) cin >> vec[i];

    int res = lisExc(k, vec);
    cout << res << '\n';
}

Ahora volveremos al algoritmo O (n log² n). Seleccione un número entero 0 <= r <= n. Defina DP '[a] [r] = max (DP [a] [b] - rb), donde se toma el máximo b, MAXB [a] [r] como el máximo b tal que DP' [a] [ r] = DP [a] [b] - rb, y MINB [a] [r] de manera similar al mínimo tal b. Mostraremos que DP [a] [k] = DP '[a] [r] + rk si y solo si MINB [a] [r] <= k <= MAXB [a] [r]. Además, mostraremos que para cualquier k existe una r para la cual se cumple esta desigualdad.

Tenga en cuenta que MINB [a] [r]> = MINB [a] [r '] y MAXB [a] [r]> = MAXB [a] [r'] si r <r ', por lo tanto, si asumimos que los dos reclamados resultados, podemos hacer una búsqueda binaria para la r, probando los valores O (log n). Por lo tanto, alcanzamos la complejidad O (n log² n) si podemos calcular DP ', MINB y MAXB en el tiempo O (n log n).

Para hacer esto, necesitaremos un árbol de segmentos que almacene las tuplas P [i] = (v_i, low_i, high_i) y admita las siguientes operaciones:

1. Dado un rango [a, b], encuentre el valor máximo en ese rango (máximo v_i, a <= i <= b), y el mínimo bajo y máximo alto emparejado con ese valor en el rango.

2. Establecer el valor de la tupla P [i]

Esto es fácil de implementar con un tiempo de complejidad O (log n) por operación, suponiendo cierta familiaridad con los árboles de segmentos. Puede consultar la implementación del algoritmo a continuación para obtener más detalles.

Ahora mostraremos cómo calcular DP ', MINB y MAXB en O (n log n). Fix r. Cree el árbol de segmentos que inicialmente contiene n + 1 valores nulos (-INF, INF, -INF). Mantenemos que P [V [j]] = (DP '[j], MINB [j], MAXB [j]) para j menos que la posición actual i. Ajuste DP '[0] = 0, MINB [0] = 0 y MAXB [0] a 0 si r> 0, de lo contrario a INF y P [0] = (DP' [0], MINB [0], MAXB [ 0]).

Lazo i de 1 a n. Hay dos tipos de subsecuencias que terminan en i: aquellas en las que el elemento anterior es mayor que V [i] y aquellas en las que es menor que V [i]. Para tener en cuenta el segundo tipo, consulte el árbol de segmentos en el rango [0, V [i]]. Deje que el resultado sea (v_1, low_1, high_1). Off1 = (v_1 + 1, low_1, high_1). Para el primer tipo, consulte el árbol de segmentos en el rango [V [i], n]. Deje que el resultado sea (v_2, low_2, high_2). Set off2 = (v_2 + 1 - r, low_2 + 1, high_2 + 1), donde incurrimos en la penalización de r por crear una excepción.

Luego combinamos off1 y off2 en off. Si off1.v> off2.v set off = off1, y si off2.v> off1.v set off = off2. De lo contrario, configure off = (off1.v, min (off1.low, off2.low), max (off1.high, off2.high)). Luego configure DP '[i] = off.v, MINB [i] = off.low, MAXB [i] = off.high y P [i] = off.

Como hacemos consultas de árbol de dos segmentos en cada i, esto toma O (n log n) en total. Es fácil demostrar por inducción que calculamos los valores correctos DP ', MINB y MAXB.

En resumen, el algoritmo es:

1. Preprocesar, modificando valores para que formen una permutación, y el último valor es el valor más grande.

2. Búsqueda binaria para la r correcta, con límites iniciales 0 <= r <= n

3. Inicialice el árbol de segmentos con valores nulos, establezca DP '[0], MINB [0] y MAXB [0].

4. Bucle de i = 1 a n, en el paso i

   • Consultar rangos [0, V [i]] y [V [i], n] del árbol de segmentos,
   • calcular DP '[i], MINB [i] y MAXB [i] en función de esas consultas, y
   • establecer el valor en la posición V [i] en el árbol de segmentos a la tupla (DP '[i], MINB [i], MAXB [i]).

5. Si MINB [n] [r] <= k <= MAXB [n] [r], devuelve DP '[n] [r] + kr - 1.

6. De lo contrario, si MAXB [n] [r] <k, la r correcta es menor que la r actual. Si MINB [n] [r]> k, la r correcta es mayor que la r actual. Actualice los límites en r y regrese al paso 1.

Aquí hay una implementación de C ++ para este algoritmo. También encuentra la subsecuencia óptima.

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    using ll = long long;
    const int INF = 2 * (int)1e9;

    pair<ll, pair<int, int>> combine(pair<ll, pair<int, int>> le, pair<ll, pair<int, int>> ri) {
        if (le.first < ri.first) swap(le, ri);
        if (ri.first == le.first) {
            le.second.first = min(le.second.first, ri.second.first);
            le.second.second = max(le.second.second, ri.second.second);
        }
        return le;
    }

    // Specialised range maximum segment tree
    class SegTree {
        private:
            vector<pair<ll, pair<int, int>>> seg;
            int h = 1;

            pair<ll, pair<int, int>> recGet(int a, int b, int i, int le, int ri) const {
                if (ri <= a || b <= le) return {-INF, {INF, -INF}};
                else if (a <= le && ri <= b) return seg[i];
                else return combine(recGet(a, b, 2*i, le, (le+ri)/2), recGet(a, b, 2*i+1, (le+ri)/2, ri));
            }
        public:
            SegTree(int n) {
                while(h < n) h *= 2;
                seg.resize(2*h, {-INF, {INF, -INF}});
            }
            void set(int i, pair<ll, pair<int, int>> off) {
                seg[i+h] = combine(seg[i+h], off);
                for (i += h; i > 1; i /= 2) seg[i/2] = combine(seg[i], seg[i^1]);
            }
            pair<ll, pair<int, int>> get(int a, int b) const {
                return recGet(a, b+1, 1, 0, h);
            }
    };

    // Binary searches index of v from sorted vector
    int bins(const vector<int>& vec, int v) {
        int low = 0;
        int high = (int)vec.size() - 1;
        while(low != high) {
            int mid = (low + high) / 2;
            if (vec[mid] < v) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    // Finds longest strictly increasing subsequence with at most k exceptions in O(n log^2 n)
    vector<int> lisExc(int k, vector<int> vec) {
        // Compress values
        vector<int> ord = vec;
        sort(ord.begin(), ord.end());
        ord.erase(unique(ord.begin(), ord.end()), ord.end());
        for (auto& v : vec) v = bins(ord, v) + 1;

        // Binary search lambda
        int n = vec.size();
        int m = ord.size() + 1;
        int lambda_0 = 0;
        int lambda_1 = n;
        while(true) {
            int lambda = (lambda_0 + lambda_1) / 2;
            SegTree seg(m);
            if (lambda > 0) seg.set(0, {0, {0, 0}});
            else seg.set(0, {0, {0, INF}});

            // Calculate DP
            vector<pair<ll, pair<int, int>>> dp(n);
            for (int i = 0; i < n; ++i) {
                auto off0 = seg.get(0, vec[i]-1); // previous < this
                off0.first += 1;

                auto off1 = seg.get(vec[i], m-1); // previous >= this
                off1.first += 1 - lambda;
                off1.second.first += 1;
                off1.second.second += 1;

                dp[i] = combine(off0, off1);
                seg.set(vec[i], dp[i]);
            }

            // Is min_b <= k <= max_b?
            auto off = seg.get(0, m-1);
            if (off.second.second < k) {
                lambda_1 = lambda - 1;
            } else if (off.second.first > k) {
                lambda_0 = lambda + 1;
            } else {
                // Construct solution
                ll r = off.first + 1;
                int v = m;
                int b = k;
                vector<int> res;
                for (int i = n-1; i >= 0; --i) {
                    if (vec[i] < v) {
                        if (r == dp[i].first + 1 && dp[i].second.first <= b && b <= dp[i].second.second) {
                            res.push_back(i);
                            r -= 1;
                            v = vec[i];
                        }
                    } else {
                        if (r == dp[i].first + 1 - lambda && dp[i].second.first <= b-1 && b-1 <= dp[i].second.second) {
                            res.push_back(i);
                            r -= 1 - lambda;
                            v = vec[i];
                            --b;
                        }
                    }
                }
                reverse(res.begin(), res.end());
                return res;
            }
        }
    }

    int main() {
        int n, k;
        cin >> n >> k;

        vector<int> vec(n);
        for (int i = 0; i < n; ++i) cin >> vec[i];

        vector<int> ans = lisExc(k, vec);
        for (auto i : ans) cout << i+1 << ' ';
        cout << '\n';
    }

Ahora probaremos las dos afirmaciones. Queremos demostrar que

1. DP '[a] [r] = DP [a] [b] - rb si y solo si MINB [a] [r] <= b <= MAXB [a] [r]

2. Para todo a, k existe un número entero r, 0 <= r <= n, tal que MINB [a] [r] <= k <= MAXB [a] [r]

Ambos se derivan de la concavidad del problema. Concavidad significa que DP [a] [k + 2] - DP [a] [k + 1] <= DP [a] [k + 1] - DP [a] [k] para todo a, k. Esto es intuitivo: cuantas más excepciones se nos permita hacer, menos nos permitirá que uno más nos ayude.

Arregle ay r. Establezca f (b) = DP [a] [b] - rb, y d (b) = f (b + 1) - f (b). Tenemos d (k + 1) <= d (k) de la concavidad del problema. Suponga que x <y y f (x) = f (y)> = f (i) para todo i. Por lo tanto, d (x) <= 0, entonces d (i) <= 0 para i en [x, y). Pero f (y) = f (x) + d (x) + d (x + 1) + ... + d (y - 1), por lo tanto d (i) = 0 para i en [x, y). Por lo tanto, f (y) = f (x) = f (i) para i en [x, y]. Esto prueba el primer reclamo.

Para probar el segundo, establezca r = DP [a] [k + 1] - DP [a] [k] y defina f, d como anteriormente. Entonces d (k) = 0, por lo tanto d (i)> = 0 para i <k y d (i) <= 0 para i> k, por lo tanto, f (k) es máximo según se desee.

Probar la concavidad es más difícil. Para una prueba, vea mi respuesta en cs.stackexchange.