Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- #define pb push_back
- #define vll vector<ll>
- using namespace std;
- int main(){
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int n;
- cin >> n;
- vll v;
- for(int i = 0; i < n; i++){
- ll x;
- cin >> x;
- v.pb(x);
- }
- pair<int, int> dp[n];
- int l = 0;
- for(int i = 0; i < n; i++){
- dp[i] = {1, 1};
- }
- for(int i = n-1; i >= 0; i--){
- if(i == n-1){
- dp[i] = {1, 1};
- l = 1;
- } else{
- for(int j = i+1; j < n; j++){
- if(v[i] > v[j]){
- if(dp[i].first <= dp[j].first){
- dp[i].first = 1+dp[j].first;
- }
- } else{
- if(dp[i].second <= dp[j].second){
- dp[i].second = 1+dp[j].second;
- }
- }
- }
- l = max(l, dp[i].first+dp[i].second-1);
- }
- }
- cout << l << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement