[数据结构与算法]AcWing 1017 怪盗基德的滑翔翼 题解（动态规划—DP—线性DP—LIS）

原题链接：https://www.acwing.com/problem/content/1019/
思路：要找出以某个点结尾的最长单调下降子序列，所以对每个点进行正反遍历两次，记录最长的下降子序列长度

#include<iostream>
#include<cstring>

using namespace std;

const int N = 110;

int n;
int f[N];
int a[N];
		
int main()
{
	cin>>n;
	while(n -- ){
		int m;
		cin>>m;
	 	int res = 0;
		for(int i = 0; i < m; i ++ ){
			cin>>a[i];
		}
		for(int i = 0; i < m; i ++ ){
			f[i] = 1;
			for(int j = 0; j < i; j ++ ){
				if(a[j] > a[i]){
					f[i] = max(f[i], f[j] + 1);
				}
				res = max(res, f[i]);
			}
		}
		memset(f, 0, sizeof f);
		for(int i = m - 1; i >= 0; i -- ){
			f[i] = 1;
			for(int j = m - 1; j > i; j -- ){
				if(a[j] > a[i]){
				    f[i] = max(f[i], f[j] + 1);
			    }
			   	res = max(res, f[i]);
			}
		}
		cout<<res<<endl;
	}
	return 0;
}