C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 508K, 提交时间: 2020-09-02 21:13:32

#pragma GCC optimize (2)
#include<bits/stdc++.h>
using namespace std;
int arr[123456];
int dp[123456];
int up[123456];
int main()
{
	int n=0,i,j;
	while(~scanf("%d",&arr[n++]));
	n--;
	
	for(i=0;i<n;i++)
	{
	dp[i]=up[i]=1;		
	}
	
	for(i=1;i<n;i++)
	{
		for(j=0;j<i;j++)
		{
			if(arr[i]<=arr[j])
			{
				dp[i]=max(dp[i],dp[j]+1);	
			}	
			else
			{
				up[i]=max(up[i],up[j]+1);
			}
		}
	}
	sort(dp,dp+n);
	sort(up,up+n);
	printf("%d\n",dp[n-1]);
	printf("%d\n",up[n-1]);
}

C++ 解法, 执行用时: 3ms, 内存消耗: 528K, 提交时间: 2021-11-27 19:49:49

#include<bits/stdc++.h>
using namespace std;
int a[30005],u[30005],d[30005];
int i,ans,cnt;
int main(){
	while(~scanf("%d",&a[i])){
		i++;
	}
	for(int k=0;k<i;k++){
		u[k]=1;
		d[k]=1;
		for(int j=0;j<k;j++){
			if(a[j]>a[k]){
				d[k]=max(d[j]+1,d[k]);
			}
			else{
				u[k]=max(u[j]+1,u[k]);
			}
		}
		ans=max(ans,d[k]);
		cnt=max(cnt,u[k]);
	}
	printf("%d\n%d",ans,cnt);
    return 0;
}