Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.3 kB
0
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

long num;
vector<long > leaders;

long cal() {

    vector<long> dpfront1(num,1) , dpback1(num,1) , dpfront2(num,1) ,dpback2(num,1);

    for(int i = 0 ; i < num ; i++){
        long x = 0 ,y = 0;
        for(int j = 0 ; j < i ; j++){
            if(leaders[i] > leaders[j]){
                x = max(x,dpfront1[j]);
            }
            else if(leaders[i] < leaders[j]){
                y = max(y,dpfront2[j]);
            }
        }
        dpfront1[i] += x;
        dpfront2[i] += y;
    }

    long res1=0,res2=0;
    for(int i = num-1;i >= 0;i--){
        long x = 0 ,y = 0;
        for(int j = num-1 ; j > i ; j--){
            if(leaders[i] > leaders[j]){
                x = max(x,dpback1[j]);
            }
            else if(leaders[i] < leaders[j]){
                y = max(y,dpback2[j]);
            }
        }
        dpback1[i] += x;
        dpback2[i] += y;
        res1 = max(res1 , dpfront1[i]+dpback1[i]-1);
        res2 = max(res2 , dpfront2[i]+dpback2[i]-1);
    }
    return max(res1,res2);
}

int main(){
    cin.tie(0);
    cin.sync_with_stdio(0);
    cin>>num;

    for(int i = 0 ; i < num ; i ++){
        long a;
        cin>>a;
        leaders.push_back(a);
    }
    cout<<cal();
	return 0;
}