¹ÖµÁ»ùµÂÊÇÒ»¸ö³äÂú´«ÆæÉ«²ÊµÄ¹ÖµÁ£¬×¨ÃÅÒÔÖ鱦ΪĿ±êµÄ³¬¼¶µÁÇÔ·¸¡£¶øËû×îΪͻ³öµÄµØ·½£¬¾ÍÊÇËûÿ´Î¶¼ÄÜÌÓÍÑÖд徯²¿µÄÖØÖØΧ¶Â£¬¶øÕâÒ²ºÜ´ó³Ì¶ÈÉÏÊǶà¿÷ÁËËûËæÉíЯ´øµÄ±ãÓÚ²Ù×÷µÄ»¬ÏèÒí¡£
ÓÐÒ»Ì죬¹ÖµÁ»ùµÂÏñÍù³£Ò»Ñù͵×ßÁËÒ»¿ÅÕä¹óµÄ×êʯ£¬²»ÁÏÈ´±»¿ÂÄÏСÅóÓÑʶÆÆÁËαװ£¬¶øËûµÄ»¬ÏèÒíµÄ¶¯Á¦×°ÖÃÒ²±»¿ÂÄÏÌß³öµÄ×ãÇòÆÆ»µÁË¡£²»µÃÒÑ£¬¹ÖµÁ»ùµÂÖ»ÄܲÙ×÷ÊÜËðµÄ»¬ÏèÒíÌÓÍÑ¡£
¼ÙÉè³ÇÊÐÖÐÒ»¹²ÓÐN´±½¨ÖþÅųÉÒ»ÌõÏߣ¬Ã¿´±½¨ÖþµÄ¸ß¶È¸÷²»Ïàͬ¡£³õʼʱ£¬¹ÖµÁ»ùµÂ¿ÉÒÔÔÚÈκÎÒ»´±½¨ÖþµÄ¶¥¶Ë¡£Ëû¿ÉÒÔÑ¡ÔñÒ»¸ö·½ÏòÌÓÅÜ£¬µ«ÊDz»ÄÜÖÐ;¸Ä±ä·½Ïò£¨ÒòΪÖÐɾ¯²¿»áÔÚºóÃæ×·»÷£©¡£ÒòΪ»¬ÏèÒí¶¯Á¦×°ÖÃÊÜËð£¬ËûÖ»ÄÜÍùÏ»¬ÐУ¨¼´£ºÖ»ÄܴӽϸߵĽ¨Öþ»¬Ïèµ½½ÏµÍµÄ½¨Öþ£©¡£ËûÏ£Íû¾¡¿ÉÄܶàµØ¾¹ý²»Í¬½¨ÖþµÄ¶¥²¿£¬ÕâÑù¿ÉÒÔ¼õ»ºÏ½µÊ±µÄ³å»÷Á¦£¬¼õÉÙÊÜÉ˵ĿÉÄÜÐÔ¡£ÇëÎÊ£¬Ëû×î¶à¿ÉÒÔ¾¹ý¶àÉÙ´±²»Í¬½¨ÖþµÄ¶¥²¿£¨°üº¬³õʼʱµÄ½¨Öþ£©£¿
ÊäÈë
ÊäÈëÊý¾ÝµÚÒ»ÐÐÊÇÒ»¸öÕûÊýK£¨K < 100£©£¬´ú±íÓÐK×é²âÊÔÊý¾Ý¡£
ÿ×é²âÊÔÊý¾Ý°üº¬Á½ÐУºµÚÒ»ÐÐÊÇÒ»¸öÕûÊýN(N < 100)£¬´ú±íÓÐN´±½¨Öþ¡£µÚ¶þÐаüº¬N¸ö²»Í¬µÄÕûÊý£¬Ã¿Ò»¸ö¶ÔÓ¦Ò»´±½¨ÖþµÄ¸ß¶Èh£¨0 < h < 10000£©£¬°´ÕÕ½¨ÖþµÄÅÅÁÐ˳Ðò¸ø³ö¡£
Êä³ö
¶ÔÓÚÿһ×é²âÊÔÊý¾Ý£¬Êä³öÒ»ÐУ¬°üº¬Ò»¸öÕûÊý£¬´ú±í¹ÖµÁ»ùµÂ×î¶à¿ÉÒÔ¾¹ýµÄ½¨ÖþÊýÁ¿¡£
ÑùÀýÊäÈë
3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10
ÑùÀýÊä³ö
6
6
9
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;
int main(int argc, char const *argv[])
{
int t;
cin >> t;
while(t--) {
int n, x, ans, m = 0, a[1005], dp[1005];
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
int j;
for(j = 1; j <= m; ++j)
if(a[i] < dp[j]) {
dp[j] = a[i];
break;
}
if(j > m) dp[++m] = a[i];
}
ans = m;
m = 0;
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; ++i) {
int j;
for(j = 1; j <= m; ++j)
if(a[i] > dp[j]) {
dp[j] = a[i];
break;
}
if(j > m) dp[++m] = a[i];
}
ans = max(m, ans);
cout << ans << endl;
}
return 0;
}