1286：怪盜基德的滑翔翼-2019-07-03(《資訊學奧賽一本通》)

#include <iostream>
#include <cstring>
#define INF 99999999
using namespace std;

int height[101], cnt[101];

int main()
{
	int k, maxn, ans1, ans2, t;
	cin >> k;
	
	while (k-- > 0)
	{
		int n;
		cin >> n;
		
		for (int i = 0; i < n; i++)
			cin >> height[i];
		
		for (int i = 0; i < n; i++)
		{
			cnt[i] = 1;
			for (int j = 0; j < i; j++)
			{
				if (height[j] > height[i] && cnt[j] + 1 > cnt[i])
					cnt[i] = cnt[j] + 1;
			}
		}
		
		maxn = 0;
		for (int i = 0; i < n; i++)
			if (cnt[i] > maxn)
				maxn = cnt[i];
		ans1 = maxn;
		
		memset(cnt, 0, sizeof(cnt));
		maxn = 0;
		
		for (int i = 0; i < n; i++)
		{
			cnt[i] = 1;
			for (int j = 0; j < i; j++)
			{
				if (height[j] < height[i] && cnt[j] + 1 > cnt[i])
					cnt[i] = cnt[j] + 1;
			}
		}
		
		maxn = 0;
		for (int i = 0; i < n; i++)
			if (cnt[i] > maxn)
				maxn = cnt[i];
		ans2 = maxn;
		
		cout << max(ans1, ans2) << endl;
		
		maxn = 0;
		memset(cnt, 0, sizeof(cnt));
		memset(height, 0, sizeof(height));
	}
	return 0;
}