Sequência da Onda

onda.cpp

#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;
}