acwing 1014 登山

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ;
const int N = 1010 ;
int f[N] ;
int dp[N] ;
int n ;
int a[N] ;
int b[N] ;
int main(){
  cin >> n ;
  for(int i = 1 ; i <= n ; i ++) cin >> a[i] ;
  for(int i = 1 ; i<= n ; i ++){
    f[i] = 1 ;
    for(int j = 1 ; j < i; j ++) {
      if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1) ;
    }
  }
  for(int i = 1 ; i <= n ; i++) b[i] = a[n-i+1] ;
  for(int i = 1 ;  i<= n ; i++){
    dp[i] = 1 ;
    for(int j = 1 ; j <i ; j++){
      if(b[j] < b[i]) dp[i] = max(dp[i],dp[j] + 1) ;
    }
  }
  int res = 0 ;
  for(int i = 1 ; i <= n ; i++) {
    //cout << f[i] << " " << dp[n-i+1] << endl ;
    res = max(res,dp[n-i+1] + f[i] - 1) ;
  }
  cout << res  << endl ;
}