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