贪心

sequence

Time Limit: 1000MS

Memory Limit: 65536KB

Description

将一个给定的数列，拆分成K个不降序列，每个数出现且只出现一次，且在各序列中各个数相对于原数列的相对顺序不变。如7 6 9 8 10可以拆成 7 9 10和6 8。求最小的K值。

Input

第一行输入一个整数T（1 <= T <= 100），表示接下来T组测试数据，每组两行，第一行为n，代表数列长度（1<=n<=10000）接下来一行有n个数，空格分隔（每个数<=50000）。

Output

对每组数据输出一个最小的K值。

Sample Input

2
5
7 6 9 8 10
5
5 4 3 2 1      
   
   

Sample Output

2
5      
    
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
int height[10000];
int main()
{
	int T;cin>>T;
	while(T--)
	{
		int n;cin>>n;
		int number;
		int p = 0;
		 for(int i=0;i<n;i++)
         {
			scanf("%d",&number);
			int tmp_index = -1;
			for (int i = 0; i < p; ++i)
			{
				if(number>=height[i] && (tmp_index == -1 || height[tmp_index] < height[i]))
				{
					tmp_index = i;
				}
			}
			if(tmp_index != -1)
			{
				height[tmp_index] = number;
			}
			else height[p++] = number;
		}
		cout<<p<<endl;
	}
}