Página Principal

MC521-1s2014

MC621-2s2014

MC521-1s2015

MC621-2s2015

MC521-1s2016

Conteúdo

Área Reservada

edit sidebar

UVA 10534

Autor: Guilherme Andrade

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>
using namespace std;


vector<int> v;
vector<int> lis;
vector<int> lds;
int n;

void fillLIS(){
        vector<int> piles;
        piles.reserve(v.size() + 100);

        for(int i=0; i < n; ++i){
                vector<int>::iterator up = lower_bound(piles.begin(), piles.end(), v[i]);
                if (up == piles.end()) {        // TODOS SAO MENORES
                        piles.push_back(v[i]);
                        lis[i] = static_cast<int>(piles.size());
                }
                else{
                        *up = v[i];
                        lis[i] = static_cast<int>(up - piles.begin()) + 1;

                }
        }

//      cout << "LIS" <<endl;
//      for(int i=0; i < n; ++i)
//              cout << "LIS["<<i<<"] = "<<lis[i] << " ";
//      cout << endl;

}

void fillLDS(){
        vector<int> piles;
        piles.reserve(v.size() + 100);

        for(int i=n-1; i >=0; --i){
                vector<int>::iterator up = lower_bound(piles.begin(), piles.end(), v[i]);
                if (up == piles.end()) {        // TODOS SAO MENORES
                        piles.push_back(v[i]);
                        lds[i] = static_cast<int>(piles.size());
                }
                else{
                        *up = v[i];
                        lds[i] = static_cast<int>(up - piles.begin()) + 1;

                }
        }
//      cout << "LDS" <<endl;
//      for(int i=0; i < n; ++i)
//              cout << "LDS["<<i<<"] = "<<lds[i] << " ";
//      cout << endl;

}



/*

20
11 9 11 9 6 11 19 18 11 20 1 13 8 3 7 3 18 1 12 1

 */

int maxWavio(const vector<int>& v){
        int _maxWavio = 1;

        fillLIS();
        fillLDS();

        for(int i=0; i < n; ++i)
                _maxWavio = max(_maxWavio,min(lis[i],lds[i])*2-1);

        return _maxWavio;
}

int main(){

        while (cin >> n) {
                v.clear();
                lis.clear();
                lds.clear();
                v.resize(n+10);
                lis.resize(n+10);
                lds.resize(n+10);
                for(int i=0; i < n; ++i)
                        cin >> v[i];

                cout << maxWavio(v) << endl;
        }


        return 0;
}