글 읽기 - [C] LIS 질문

shawn050912 6년 전 0

이렇게 풀면 잘 푼 것 같은데 자꾸 시간초과가 뜹니다... 틀리면 인정을 하겠지만 시간초과이기 때문에 시간초과가 나는 이유와 만약 고칠 수 없이 소스가 저세상으로 가벼렷으면 다른 방법만 설명해주세요.

#include <stdio.h>
int d[1003]={0},m[1003]={0},f[1003]={0},p[1003]={0};
int main()
{
	int n,i,j,max=0,maxp;
	
	scanf("%d",&n);
	for(i=1; i<=n; i++) scanf("%d",&d[i]);
	for(i=1; i<=n; i++){
		for(j=0; j<i; j++){
			if(d[j]<d[i] && m[j]>max) max=m[j],maxp=j;
			else if(m[j]==max && d[maxp]>d[j]) max=m[j],maxp=j;
		}
		if(max!=0) m[i]=max+1,f[i]=maxp;
		else m[i]=1;
		max=0;
	}
	maxp=0;
	for(i=1; i<=n; i++){
		if(m[i]>max) max=m[i],maxp=i;
		else if(m[i]==max && d[i]<d[maxp]) max=m[i],maxp=i;
	}
	printf("%d\n",m[i]);
	return 0;
}