using namespace std;

const int maxn=1010;

int h[maxn],f[maxn];

int main()

{

int n;

cin>>n;

for(int i=0;i<n;i++)

cin>>h[i];

//输入

for(int i=0;i<n;i++)

f[i]=1;

for(int i=1;i<n;i++)

for(int j=0;j<i;j++)

if(h[i]<=h[j] && f[i]<(f[j]+1))

f[i]=f[j]+1;

int ans=0;

for(int i=n-1;i>=0;i--)

ans=(ans<f[i])?f[i]:ans;

cout<<ans<<' ';

//求最长不上升子序列

for(int i=0;i<n;i++)

f[i]=1;

for(int i=1;i<n;i++)

for(int j=0;j<i;j++)

if(h[i]>h[j] && f[i]<(f[j]+1))

f[i]=f[j]+1;

ans=0;

for(int i=n-1;i>=0;i--)

ans=(ans<f[i])?f[i]:ans;

cout<<ans<<endl;

//求最长上升子序列

// system("pause");

return 0;

}

至于第二问为什么要求最长上升子序列，可以参考

http://cjoiemoi.is-programmer.com/posts/32339.html

讲得很详细。