uva 10534 - Wavio Sequence

/*

Problem link
Type: DP, LIS, LDS
Algorithm: 
 - Find the LIS and save the LIS til index i in array d1.
 - Find the LDS by do the LIS backward and save the LDS till index i in array d2.
 - For each element, consider it as the top element of the waivo.
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;
const int maxn = 10010;
//-------------------------------
int a[maxn], lis[maxn],d1[maxn],d2[maxn];
int n;
//-------------------------------
int BSearch(int i, int j, int x) {
 int l,r,m;
 l = i; r = j;
 do
 {
  m = (l+r)/2;
  if (lis[m]>=x) r = m;
  else l = m;
 } while (r-l>1);
 if (lis[l]>=x) return(l);
 else if (lis[r]>=x) return(r);
 else return(-1);
}
//-------------------------------
void solve() {
 int result = 0;
 for (int i=1; i<=n; i++) 
 {
  int pos = BSearch(1,result,a[i]);
  if (pos==-1) lis[++result] = a[i];
  else lis[pos] = a[i];
  d1[i] = result;
 }
 result = 0;
 for (int i=n; i>=1; i--)
 {
  int pos = BSearch(1,result,a[i]);
  if (pos==-1) lis[++result] = a[i];
  else lis[pos] = a[i];
  d2[i] = result;
 }
 result = 1;
 for (int i=1; i<=n; i++)
  result = max(result,min(d1[i],d2[i]));
 cout << result*2-1 << endl;
}
//-------------------------------
int main() {
 while (!cin.eof()) 
 {
  cin >> n;
  if (cin.eof()) break;
  for (int i=1; i<=n; i++) cin >> a[i];
  solve();  
 }
 return 0;
}
//-------------------------------