Maiores sequências crescentes em K

Por que eu criei um thread duplicado

Eu criei esse segmento depois de ler Maior subsequência crescente com K exceções permitidas . Percebi que a pessoa que estava fazendo a pergunta realmente não havia entendido o problema, porque estava se referindo a um link que resolve o problema "Subtrade de maior aumento com uma alteração permitida". Portanto, as respostas que ele obteve foram irrelevantes para o problema do LIS.

Descrição do problema

Suponha-se que uma matriz A é dada com comprimento N . Encontre a subseqüência crescente mais longa com K exceções permitidas.

Exemplo
1) N = 9, K = 1

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

Resposta: 7

Explicação:

A subsequência crescente mais longa é: 3,4,5,8 (ou 6), 1 (exceção), 3,7 -> total = 7

2) N = 11, K = 2

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

resposta: 8

O que eu fiz até agora ...

Se K = 1, apenas uma exceção é permitida. Se o algoritmo conhecido para calcular a Subseqüência Crescente Mais Longa em O (NlogN) for usado ( clique aqui para ver esse algoritmo ), poderemos calcular o LIS começando de A [0] a A [N-1] para cada elemento da matriz A. guardar os resultados de uma nova matriz G com tamanho N . Olhando para o exemplo n.1, a matriz L seria: L = [1,2,2,3,4,4,4,4,5].

Utilizando a lógica reversa, calculamos a matriz R , cada elemento contendo a atual Sequência Decrescente Mais Longa de N-1 a 0.

O LIS com uma exceção é apenas sol = max (sol, L [i] + R [i + 1]), onde sol é inicializado como sol = L [N-1] . Portanto, calculamos o LIS de 0 até um índice i (exceção), paramos e iniciamos um novo LIS até 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

-> explicação passo a passo:

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

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

porque as matrizes R, L precisam de tempo NlogN para calcular e também precisamos de Θ (N) para encontrar sol .

Código para o problema k = 1

#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;
}

Generalização para K exceções

Eu forneci um algoritmo para K = 1. Não tenho idéia de como alterar o algoritmo acima para trabalhar com K exceções. Eu ficaria feliz se alguém pudesse me ajudar.

( PS. Se necessário, posso fornecer código para o algoritmo K = 1 em C ++.)

Esta resposta foi modificada da minha resposta para uma pergunta semelhante no Computer Science Stackexchange.

O problema do LIS com no máximo k exceções admite um algoritmo O (n log² n) usando relaxação Lagrangiana. Quando k é maior que log n, isso melhora assintoticamente no O (nk log n) DP, o que também explicaremos brevemente.

Seja DP [a] [b] denotando o comprimento da subsequência crescente mais longa com no máximo b exceções (posições em que o número inteiro anterior é maior que o próximo) terminando no elemento b a. Esse DP não está envolvido no algoritmo, mas sua definição facilita a prova do algoritmo.

Por conveniência, assumiremos que todos os elementos são distintos e que o último elemento da matriz é o máximo. Observe que isso não nos limita, pois podemos adicionar m / 2n à m-ésima aparência de cada número e acrescentar infinito à matriz e subtrair um da resposta. Seja V a permutação pela qual 1 <= V [i] <= n é o valor do i-ésimo elemento.

Para resolver o problema em O (nk log n), mantemos a invariante de que DP [a] [b] foi calculado para b <j. Loop j de 0 a k, na j-ésima iteração calculando DP [a] [j] para todos a. Para fazer isso, faça um loop i de 1 a n. Mantemos o máximo de DP [x] [j-1] acima de x <ie um prefixo máximo de estrutura de dados que no índice i terá DP [x] [j] na posição V [x] para x <ie 0 em qualquer outra posição.

Temos DP [i] [j] = 1 + max (DP [i '] [j], DP [x] [j-1]) onde examinamos i', x <i, V [i '] < V [i]. O prefixo máximo de DP [x] [j-1] nos fornece o máximo de termos do segundo tipo, e a consulta da estrutura de dados máxima do prefixo para o prefixo [0, V [i]] nos fornece o máximo de termos do primeiro tipo. Atualize o prefixo máximo e a estrutura máxima de dados do prefixo.

Aqui está uma implementação do algoritmo em C ++. Observe que esta implementação não pressupõe que o último elemento da matriz seja o máximo ou que a matriz não contém duplicatas.

#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';
}

Agora retornaremos ao algoritmo O (n log² n). Selecione algum número inteiro 0 <= r <= n. Defina DP '[a] [r] = max (DP [a] [b] - rb), onde o máximo é retomado b, MAXB [a] [r] como o máximo b, de modo que DP' [a] [ r] = DP [a] [b] - rb e MINB [a] [r] da mesma forma que o mínimo tal b. Mostraremos que DP [a] [k] = DP '[a] [r] + rk se e somente se MINB [a] [r] <= k <= MAXB [a] [r]. Além disso, mostraremos que para qualquer k existe um r para o qual essa desigualdade é válida.

Observe que MINB [a] [r]> = MINB [a] [r '] e MAXB [a] [r]> = MAXB [a] [r'] se r <r '; portanto, se assumirmos as duas reivindicações resultados, podemos fazer uma pesquisa binária para r, tentando valores O (log n). Portanto, atingimos a complexidade O (n log² n) se pudermos calcular DP ', MINB e MAXB em O (n log n).

Para fazer isso, precisaremos de uma árvore de segmentos que armazene tuplas P [i] = (v_i, baixo_i, alto_i) e suporte as seguintes operações:

1. Dado um intervalo [a, b], encontre o valor máximo nesse intervalo (máximo v_i, a <= i <= b) e o mínimo baixo e o máximo alto emparelhados com esse valor no intervalo.

2. Defina o valor da tupla P [i]

É fácil de implementar com complexidade O (log n) tempo por operação, assumindo alguma familiaridade com as árvores de segmentos. Você pode consultar a implementação do algoritmo abaixo para obter detalhes.

Vamos agora mostrar como calcular DP ', MINB e MAXB em O (n log n). Corrigir r. Crie a árvore de segmentos inicialmente contendo n + 1 valores nulos (-INF, INF, -INF). Mantemos que P [V [j]] = (DP '[j], MINB [j], MAXB [j]) para j menor que a posição atual i. Defina DP '[0] = 0, MINB [0] = 0 e MAXB [0] para 0 se r> 0, caso contrário, para INF e P [0] = (DP' [0], MINB [0], MAXB [ 0]).

Loop i de 1 a n. Existem dois tipos de subsequências que terminam em i: aquelas em que o elemento anterior é maior que V [i] e aquelas em que é menor que V [i]. Para explicar o segundo tipo, consulte a árvore de segmentos no intervalo [0, V [i]]. Seja o resultado (v_1, baixo_1, alto_1). Desativar1 = (v_1 + 1, baixo_1, alto_1). Para o primeiro tipo, consulte a árvore de segmentos no intervalo [V [i], n]. Seja o resultado (v_2, baixo_2, alto_2). Defina off2 = (v_2 + 1 - r, baixo_2 + 1, alto_2 + 1), onde incorremos na penalidade de r por criar uma exceção.

Então combinamos off1 e off2 em off. Se off1.v> off2.v ativar = off1, e se off2.v> off1.v ativar = off2. Caso contrário, defina = (off1.v, min (off1.low, off2.low), max (off1.high, off2.high)). Em seguida, defina DP '[i] = desligado.v, MINB [i] = desligado.baixo, MAXB [i] = desligado.alta e P [i] = desligado.

Como fazemos duas consultas em árvore de segmento a cada i, isso leva tempo O (n log n) no total. É fácil provar por indução que calculamos os valores corretos DP ', MINB e MAXB.

Então, resumindo, o algoritmo é:

1. Pré-processe, modificando valores para que eles formem uma permutação e o último valor seja o maior valor.

2. Pesquisa binária pelo r correto, com limites iniciais 0 <= r <= n

3. Inicialize a árvore de segmentos com valores nulos, defina DP '[0], MINB [0] e MAXB [0].

4. Loop de i = 1 para n, na etapa i

   • Consultar intervalos [0, V [i]] e [V [i], n] da árvore de segmentos,
   • calcular DP '[i], MINB [i] e MAXB [i] com base nessas consultas, e
   • ajustando o valor na posição V [i] na árvore de segmentos para a tupla (DP '[i], MINB [i], MAXB [i]).

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

6. Caso contrário, se MAXB [n] [r] <k, o r correto for menor que o atual r. Se MINB [n] [r]> k, o r correto for maior que o atual r. Atualize os limites em re retorne à etapa 1.

Aqui está uma implementação C ++ para esse algoritmo. Ele também encontra a subsequência ideal.

    #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';
    }

Agora provaremos as duas reivindicações. Queremos provar que

1. DP '[a] [r] = DP [a] [b] - rb se e somente se MINB [a] [r] <= b <= MAXB [a] [r]

2. Para todo a, k existe um número inteiro r, 0 <= r <= n, de modo que MINB [a] [r] <= k <= MAXB [a] [r]

Ambos seguem a concavidade do problema. Concavidade significa que DP [a] [k + 2] - DP [a] [k + 1] <= DP [a] [k + 1] - DP [a] [k] para todos os a, k. Isso é intuitivo: quanto mais exceções tivermos permissão para fazer, menor será a permissão de mais uma.

Corrija a e r. Defina f (b) = DP [a] [b] - rb e d (b) = f (b + 1) - f (b). Temos d (k + 1) <= d (k) da concavidade do problema. Suponha x <yef (x) = f (y)> = f (i) para todos i. Portanto, d (x) <= 0, portanto d (i) <= 0 para i em [x, y). Mas f (y) = f (x) + d (x) + d (x + 1) + ... + d (y - 1), portanto d (i) = 0 para i em [x, y). Portanto, f (y) = f (x) = f (i) para i em [x, y]. Isso prova a primeira reivindicação.

Para provar o segundo, defina r = DP [a] [k + 1] - DP [a] [k] e defina f, d como anteriormente. Então d (k) = 0, portanto d (i)> = 0 para i <ke ed (i) <= 0 para i> k, portanto, f (k) é o máximo, conforme desejado.

Provar concavidade é mais difícil. Para uma prova, veja minha resposta em cs.stackexchange.