Numéro de l'accroissement de sous-séquences dans la séquence donnée?

Vous pouvez calculer le nombre croissant de sous-séquences en O(n log n) comme suit.

Rappel de l'algorithme pour la longueur de la plus longue sous-suite croissante:

Pour chaque élément, calculer le prédécesseur élément parmi les éléments précédents, et ajouter à cela la longueur.

Cet algorithme s'exécute naïvement en O(n^2), et s'exécute en O(n log n) (ou encore mieux, dans le cas des nombres entiers), si vous calculez le prédécesseur à l'aide d'une structure de données comme un équilibre binaire un arbre de recherche (BST) (ou quelque chose de plus avancé comme un van Emde Boas arbre pour les entiers).

De modifier cet algorithme pour le calcul du nombre de séquences, de les stocker dans la BST dans chaque nœud, le nombre de séquences se terminant à cet élément. Lors du traitement de l'élément suivant dans la liste, il vous suffit de rechercher le prédécesseur, compter le nombre de séquences se terminant à un élément qui est inférieur à l'élément en cours de traitement (en O(log n) le temps), et stocker le résultat dans la BST avec l'élément courant. Enfin, vous avez la somme des résultats pour chaque élément de l'arborescence pour obtenir le résultat.

Comme une mise en garde, note que le nombre croissant de séquences pourraient être très grande, de sorte que l'arithmétique ne prend plus de O(1) fois par opération. Cela doit être pris en considération.

Psuedocode:

ret = 0
T = empty_augmented_bst() //with an integer field in addition to the key
for x int X:

  //sum of auxiliary fields of keys less than x
  //computed in O(log n) time using augmented BSTs
  count = 1 + T.sum_less(x)

  T.insert(x, 1 + count) //sets x's auxiliary field to 1 + count
  ret += count //keep track of return value

return ret

OriginalL'auteur jonderry

C'est un O(nklogn) solution où n est la longueur du tableau d'entrée et k est la taille de l'augmentation de la sous-séquences. Il est basé sur le solution mentionnée dans la question.

vector<int> values, un n longueur de la matrice, est la matrice pour la recherche croissante de sous-séquences.

vector<int> temp(n); //Array for sorting
map<int, int> mapIndex; //This will translate from the value in index to the 1-based count of values less than it

partial_sort_copy(values.cbegin(), values.cend(), temp.begin(), temp.end());

for(auto i = 0; i < n; ++i){
    mapIndex.insert(make_pair(temp[i], i + 1)); //insert will only allow each number to be added to the map the first time
}

mapIndex contient maintenant un classement de tous les numéros de values.

vector<vector<int>> binaryIndexTree(k, vector<int>(n)); //A 2D binary index tree with depth k
auto result = 0;

for(auto it = values.cbegin(); it != values.cend(); ++it){
    auto rank = mapIndex[*it];
    auto value = 1; //Number of sequences to be added to this rank and all subsequent ranks
    update(rank, value, binaryIndexTree[0]); //Populate the binary index tree for sub-sequences of length 1

    for(auto i = 1; i < k; ++i){ //Itterate over all sub-sequence lengths 2 - k
        value = getValue(rank - 1, binaryIndexTree[i - 1]); //Retrieve all possible shorter sub-sequences of lesser or equal rank
        update(rank, value, binaryIndexTree[i]); //Update the binary index tree for sub sequences of this length
    }
    result += value; //Add the possible sub-sequences of length k for this rank
}

Après avoir placé tous les n éléments de values dans tous les k dimensions de binaryIndexTree. Le values recueillies dans result représentent le nombre total de l'augmentation de la sous-séquences de longueur k.

L'index binaire des fonctions d'arbre utilisé pour obtenir ce résultat sont:

void update(int rank, int increment, vector<int>& binaryIndexTree)
{
    while (rank < binaryIndexTree.size()) { //Increment the current rank and all higher ranks
        binaryIndexTree[rank - 1] += increment;
        rank += (rank & -rank);
    }
}

int getValue(int rank, const vector<int>& binaryIndexTree)
{
    auto result = 0;
    while (rank > 0) { //Search the current rank and all lower ranks
        result += binaryIndexTree[rank - 1]; //Sum any value found into result
        rank -= (rank & -rank);
    }
    return result;
}

L'index binaire arbre est évidemment O(nklogn), mais c'est la capacité de manière séquentielle remplir qui crée la possibilité de l'utiliser pour une solution.

mapIndex crée un classement pour chaque nombre dans values, de telle sorte que le plus petit nombre dans values a un rang de 1. (Par exemple si values est "2, 3, 4, 3, 4, 1" puis mapIndex contiendra: "{1, 1}, {2, 2}, {3, 3}, {4, 5}". Notez que "4" a un rang de "5" car il y a 2 "3"s dans values

binaryIndexTree a k différents arbres, niveau x représentent le nombre total d'augmenter les sous-chaînes de caractères qui peuvent être formés de longueur x. N'importe quel nombre dans values pouvez créer une sous-chaîne de longueur 1, de sorte que chaque élément de l'incrémenter de rang et tous les rangs au-dessus de 1.

À des niveaux supérieurs, une augmentation de la sous-chaîne dépend il y a déjà une sous-chaîne de longueur plus courte et de rang inférieur.

Parce que les éléments sont insérés dans l'index binaire de l'arbre en fonction de leur ordre dans values, l'ordre d'apparition dans values est préservée, de sorte que si un élément a été inséré dans binaryIndexTree c'est parce qu'elle a précédé l'élément en cours dans values.

Une excellente description de la façon dont binaire arbre d'index est disponible ici: http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

Vous pouvez trouver une version exécutable du code ici: http://ideone.com/GdF0me

OriginalL'auteur Jonathan Mee

Version de Java comme un exemple:

    int[] A = {1, 2, 0, 0, 0, 4};
    int[] dp = new int[A.length];

    for (int i = 0; i < A.length; i++) {
        dp[i] = 1;

        for (int j = 0; j <= i - 1; j++) {
            if (A[j] < A[i]) {
                dp[i] = dp[i] + dp[j];
            }
        }
    }

OriginalL'auteur Ivan Voroshilin