Numero di Successioni crescenti di lunghezza k

Question

Sto cercando di capire l'algoritmo che mi dà il numero di sottosequenze crescenti di lunghezza K in un array nel tempo O (n k log (n)). So come risolvere questo stesso problema usando l'algoritmo O (k * n^2). Ho cercato e ho scoperto che questa soluzione utilizza BIT (Fenwick Tree) e DP. Ho anche trovato del codice, ma non sono stato in grado di capirlo.

Ecco alcuni link che ho visitato che sono stati utili.

Here in SO
Topcoder forum
Random webpage

sarei davvero grato se qualcuno mi può aiutare a capire questo algoritmo.

Answer 1

sto riproducendo il mio algoritmo da here, in cui si tratta la sua logica:

dp[i, j] = same as before num[i] = how many subsequences that end with i (element, not index this time) 
     have a certain length 

for i = 1 to n do dp[i, 1] = 1 

for p = 2 to k do // for each length this time num = {0} 

    for i = 2 to n do 
    // note: dp[1, p > 1] = 0 

    // how many that end with the previous element 
    // have length p - 1 
    num[ array[i - 1] ] += dp[i - 1, p - 1] *1* 

    // append the current element to all those smaller than it 
    // that end an increasing subsequence of length p - 1, 
    // creating an increasing subsequence of length p 
    for j = 1 to array[i] - 1 do *2*  
     dp[i, p] += num[j] 

È possibile ottimizzare *1* e *2* utilizzando alberi di segmento o alberi indicizzati binari. Questi saranno utilizzati per elaborare in modo efficiente le seguenti operazioni sull'array num:

• Dato (x, v) aggiungi v a num[x] (rilevante per *1*);
• Dato x, trovare la somma num[1] + num[2] + ... + num[x] (rilevante per *2*).

Questi sono problemi banali per entrambe le strutture di dati.

Nota: Ciò avrà complessità O(n*k*log S), dove S è il limite superiore per i valori nel vostro array. Questo può o non può essere abbastanza buono. Per renderlo O(n*k*log n), è necessario normalizzare i valori dell'array prima di eseguire l'algoritmo di cui sopra. Normalizzazione significa convertire tutti i valori dell'array in valori inferiori o uguali a n. Quindi questo:

5235 223 1000 40 40 

diventa:

4 2 3 1 1 

questo può essere realizzato con una specie (mantenere gli indici originali).