2013noip day2 第二题，挺简单的dp
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100000+10;
int n;
int a[maxn],f[maxn],g[maxn];
void init()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
}
void readdata()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
g[i]=1;
f[i]=1;
}
}
void work()
{
for(int i=2;i<=n;i++)
{
for(int j=i-1;j>0;j--)
{
if(a[j] > a[i])
{
f[i]=max(g[j]+1,f[i]);
}
if(a[j] == a[i])
{
f[i]=max(f[i],f[j]);
g[i]=max(g[i],g[j]);
}
if(a[j] < a[i])
{
g[i]=max(g[i],f[j]+1);
}
}
}
int m=1;
for(int i=1;i<=n;i++) m=max(m,max(f[i],g[i]));
printf("%d",m);
}
int main()
{
readdata();
work();
return 0;
}
