Solution UVA: 10534 - Wavio Sequence

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10534 - Wavio Sequence	Accepted	C++11	1.800	0.010	3687	1 mins ago

Suggest:

- L[i] = Longest Increasing Subsequence 1->n 

- R[i] = Longest Increasing Subsequence n->1

=> res= max(res, min(L[i], R[i])*2 - 1)

#include<bits/stdc++.h>

using namespace std;

int n;

typedef pair<int, int> ii;

vector<int> dp(const vector<int> &a){

    set<ii> myset;

    vector<int> L(n);

   

    auto comp = [](const std::pair<int, int>& p, int x) {

        return p.first < x;

    };

   

    for(int i=0; i<n; i++){

   

        L[i]= 1;        

        if (myset.empty()){

            myset.insert(make_pair(a[i], L[i]));

            continue;

        }

       

        auto it = std::lower_bound(myset.begin(), myset.end(), a[i], comp);

       

        if (it==myset.begin()) myset.insert({a[i], L[i]});

        else{

       

            it--;

            L[i] += it->second;

           

            auto jt= it;

            do{

               

                it++;

                if (it == myset.end()) break;

                if (it->second <= L[i]){

                   

                    myset.erase(it);

                    it = jt;    

                }  

                else break;

           

            }while(1);

           

            myset.insert({a[i], L[i]});    

        }

   

    }

   

    return L;

}

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

    while(cin >> n){

       

        vector<int> a(n), L, R;

        for(int i=0; i<n; i++)

            cin >> a[i];

           

        L = dp(a);

        reverse(a.begin(), a.end());

        R = dp(a);

        reverse(R.begin(), R.end());

       

        int res= 0;

        for(int i=0; i<n; i++)

            res= max(res, min(L[i], R[i])*2 - 1);  

        cout<<res<<"\n";

    }

}