15. LIS

알고라파덕


LIS 소스.
#include <stdio.h>

void LIS();
int cnt[510][510];
int main()
{
	int testcase;
	scanf("%d", &testcase);
	while(testcase >= 1)
	{
		--testcase;
		LIS();
	}
	return 0;
}
void LIS()
{
	int num[510];
	int N, M, i, j, max = 0;
	scanf("%d", &N);
	for(i=1; i<=N; i++) scanf("%d", &num[i]);
	for(i=1; i<=N; i++)
	{
		if(num[1] < num[i]) cnt[1][i] = 2;
		else cnt[1][i] = 1;
	}
	for(i=2; i<=N; i++)
	{
		for(j=1; j<=i; j++)
			cnt[i][j] = cnt[i-1][j];
		for(j=i+1; j<=N; j++)
		{
			if(num[i] > num[j]) cnt[i][j] = cnt[i-1][j];
			else
			{
				if(cnt[i][i] + 1 < cnt[i-1][j]) cnt[i][j] = cnt[i-1][j];
				else cnt[i][j] = cnt[i][i]+1;
			}
		}
	}
	max = 0;
	for(i=1; i<=N; i++) 
		if(max < cnt[N][i]) 
			max = cnt[N][i];

	printf("%d\n", max);
	for(i=1; i<=N; i++)
		for(j=1; j<=N; j++)
			cnt[i][j] = 0;

}