subsequência não decrescente mais longa em O (nlgn)
Eu tenho o seguinte algoritmo que funciona bem
Eu tentei explicar aqui por mim mesmohttp://nemo.la/?p=943 e é explicado aquihttp://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/ bem e no stackoverflow também
Quero modificá-lo para produzir a subsequência não monotonicamente crescente mais longa
para a sequência 30 20 20 10 10 10 10
a resposta deve ser 4: "10 10 10 10"
Mas a versão with nlgn do algoritmo não está funcionando. Inicializando s para conter o primeiro elemento "30" e começando no segundo elemento = 20. É o que acontece:
O primeiro passo: 30 não é maior que ou igual a 20. Encontramos o menor elemento maior que 20. O novo s se torna "20"
O segundo passo: 20 é maior ou igual a 20. Estendemos a sequência es agora contém "20 20"
O terceiro passo: 10 não é maior que ou igual a 20. Encontramos o menor elemento maior que 10, que é "20". O novo s se torna "10 20"
es nunca crescerá depois disso e o algoritmo retornará 2 em vez de 4
int height[100];
int s[100];
int binary_search(int first, int last, int x) {
int mid;
while (first < last) {
mid = (first + last) / 2;
if (height[s[mid]] == x)
return mid;
else if (height[s[mid]] >= x)
last = mid;
else
first = mid + 1;
}
return first; /* or last */
}
int longest_increasing_subsequence_nlgn(int n) {
int i, k, index;
memset(s, 0, sizeof(s));
index = 1;
s[1] = 0; /* s[i] = 0 is the index of the element that ends an increasing sequence of length i = 1 */
for (i = 1; i < n; i++) {
if (height[i] >= height[s[index]]) { /* larger element, extend the sequence */
index++; /* increase the length of my subsequence */
s[index] = i; /* the current doll ends my subsequence */
}
/* else find the smallest element in s >= a[i], basically insert a[i] in s such that s stays sorted */
else {
k = binary_search(1, index, height[i]);
if (height[s[k]] >= height[i]) { /* if truly >= greater */
s[k] = i;
}
}
}
return index;
}