登山-题解

算法原理和合唱队形一模一样，都是求出序列的LIS和LNIS，详细算法可以看题解合唱队形题解
只不过要注意！合唱队形输出的是要出列的(相当于没登上的山)，而这道题要输出的是登上的山
所以输出的是maxn-1

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005];
int DP_lis[1005];
int DP_lnis[1005];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){cin>>a[i];}
	for(int i=1;i<=n;i++){
		DP_lis[i]=1;
		for(int j=1;j<=i-1;j++){
			if(a[i]>a[j]&&DP_lis[j]+1>DP_lis[i]){DP_lis[i]=DP_lis[j]+1;}
		}
	}
	for(int i=n;i>=1;i--){
		DP_lnis[i]=1;
		for(int j=i+1;j<=n;j++){
			if(a[j]<a[i]&&DP_lnis[j]+1>DP_lnis[i]){DP_lnis[i]=DP_lnis[j]+1;}
		}
	}
	int maxn=0;
	for(int i=1;i<=n;i++){
		maxn=max(DP_lis[i]+DP_lnis[i],maxn);
	} 
	cout<<maxn-1;
	/*Debug
	for(int i=1;i<=n;i++){
		cout<<DP_lis[i]<<' ';
	}cout<<endl;
	for(int i=1;i<=n;i++){
		cout<<DP_lnis[i]<<' ';
	}cout<<endl;
	*/
	return 0;
}