백준 14002 - 가장 긴 증가하는 부분 수열4

[ 백준 14002 - 가장 긴 증가하는 부분 수열4 ]

https://www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

#include <stdio.h>
#include <string.h>
int main()
{

	int a[1001]={0,};
	int dy[1001]={0,}, path[1001]={0,};
	int stack[1010]={0,};
	int n, i, j, k=0, l, top=0;

	scanf("%d", &n);
	for(i=0;i<n;i++)
	{
		scanf("%d", &a[i]);
	} 
	
	for(i=0;i<n;i++)
	{
		dy[i]=1;
		path[i]=-1;
		for(j=0;j<i;j++)
		{
			if(a[i]>a[j] && dy[j]+1>dy[i])
			{
				dy[i]=dy[j]+1;
				path[i]=j;     
			}
		}
		if(k<dy[i])
		{
			k=dy[i];
			l=i;
		}
	}

	do{
		stack[top]=a[l];
		l=path[l];
		top++;
		if(l==-1)
		{
			break;
		}
	}while(1);
    
	printf("%d\n", k);
    
	do{
		top--;
		if(top==-1)
		{
			break;
		}
		printf("%d ", stack[top]);
	}while(1);

	return 0;

}