题意:
给你一排房屋,每个房屋的高度都是任意的,你可以选择从任何一栋楼出发并决定方向,方向一旦决定便不能被改变,让你求最长下降子序列。
分析:
可以设置两个数组,求一遍上升子序列,求一遍下降子序列,然后求个最大值就好,因为是可以从任意点出发,所以说每个点都有可能是最大值,求个max即可。下面请看代码:
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int f[N],h[N];
int main() {
int T;
cin>>T;
while(T--) {
memset(f,0,sizeof f);
int n;
cin>>n;
for(int i=1; i<=n; i++) cin>>h[i];
int ans = 0;
for(int i=1; i<=n; i++) {
f[i] = 1;
for(int j=1; j<i; j++) {
if(h[i] < h[j]) f[i] = max(f[i],f[j]+1);
}
ans = max(ans,f[i]);
}
memset(f,0,sizeof f);
for(int i=n; i>=1; i--) {
f[i] = 1;
for(int j=n; j>i; j--) {
if(h[i] < h[j]) f[i] = max(f[i],f[j]+1);
}
ans = max(ans,f[i]);
}
cout<<ans<<endl;
}
return 0;
}