Solução Sequência da Onda

Código de Roger Benet, comentários de Rogério Júnior

Para ver o problema original, clique aqui. Esta é uma questão muito simples de LIS (Maior Subsequência Crescente). Se você não conhece este algoritmo, clique aqui para ver a Aula de LIS do Curso Noic. Quando estamos fazendo o algoritmo da LIS, o número da pilha em que colocamos o elemento que estamos processando é exatamente o tamanho da maior subsequência crescente que termina exatamente nele, logo podemos usar o algoritmo da LIS para sabermos a maior sequência crescente que termina em cada elemento e depois fazemos o algoritmo de traz para frente para encontrarmos a maior subsequência decrescente que começa em cada elemento.

Supondo agora que sabemos, para um dado elemento na posição i da sequência, o tamanho da maior subsequência crescente que termina nele (digamos cresc_i) e da maior subsequência decrescente que começa nele (digamos decres_i), a maior Sequência da Onda que podemos criar tendo i como elemento central é justamente usando todos os elementos de min(cresc_i, \ decresc_i) e o maior número de elementos possível de max(cresc_i, \ decresc_i) (que é exatamente min(cresc_i, \ decresc_i)), lembrando de subtrair 1 porque contamos o elemento i duas vezes (o fim da crescente e o começo da decrescente).

Deste modo, a maior Sequência da Onda que tenha i como elemento central terá 2 \times min(cresc_i, \ decresc_i)-1 elementos. Basta calcularmos este valor para todos os valores de i de 1 a n e imprimirmos o maior. Segue o código para melhor entendimento:


#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 10100
int vet[MAX], n, lc[MAX], ld[MAX], M[MAX];
// Algoritmos de LIS
// na ordem normal
void lis_cres(){
int L = 0;
for(int i = 1; i <= n; i++){
int lo = 1;
int hi = L;
while(lo <= hi){
int mid = (lo+hi)/2;
if (vet[M[mid]] < vet[i])lo = mid+1;
else hi = mid-1;
}
int newL = lo;
M[newL] = i;
L = max(L, newL);
// guardo o tamanho da maior subsequência crescente
// que acaba em i, em lc[i]
lc[i] = L;
}
}
// e de trás para frente
void lis_decres(){
int L = 0;
for(int i = n; i >= 1; i--){
int lo = 1;
int hi = L;
while(lo <= hi){
int mid = (lo+hi)/2;
if (vet[M[mid]] < vet[i])lo = mid+1;
else hi = mid-1;
}
int newL = lo;
M[newL] = i;
L = max(L, newL);
// guardo o tamanho da maior subsequência decrescente
// que começa em i, em lc[i]
ld[i] = L;
}
}
int main(){
// enquanto houver entrada
while(scanf("%d", &n) != EOF){
// leio a sequência da entrada
for(int i = 1; i <= n; i++) scanf("%d", &vet[i]);
// faço a LIS normal
lis_cres();
// e de trá para frente
lis_decres();
int ans = 0;
// percorro todas as posições, procurando qual delas é o meio
// da maior sequência da onda
for(int i = 1; i <= n; i++) ans = max(ans, 2*min(lc[i], ld[i])-1);
// e imprimo a resposta
printf("%d\n",ans);
}
return 0;
}

view raw

onda.cpp

hosted with ❤ by GitHub