怪盗基德的滑翔翼

怪盗基德的滑翔翼
题目概述：怪盗基德可以选择一个方向，并沿着该方向进行滑行，规定他只能从较高的楼房移动到较低的楼房，问他最多可以走过多少栋楼房。
解题思路：很容易将该题抽象为最长上升子序列模型，需要注意的是本题可以选择滑行的方向，也就是正反方向分别进行dp，取最大值

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
const int N = 110;

int h[N];
int f[N],g[N];

void solve(){
	int n;
	cin >> n;

	for(int i = 1; i <= n; i ++)cin >> h[i];

	int res = 0;
  //正向操作
	for(int i = 1; i <= n; i ++){
		f[i] = 1;
		for(int j = 1; j < i; j ++){
			
			if(h[j] < h[i])f[i] = max(f[i],f[j] + 1);
		}
	}
//反向操作
	for(int i = n; i >= 1; i --){
		g[i] = 1;
		for(int j = n; j > i; j --){
			
			if(h[j] < h[i])g[i] = max(g[i],g[j] + 1);
		}
	}

	for(int i = 1; i <= n; i ++)res = max({res,f[i],g[i]});
	cout << res << endl;
}

int main(){
	int T;
	cin >> T;

	while(T --){
		solve();
	}
	
}