11053 : 가장 긴 증가하는 부분

#include<stdio.h>

int main(void){
	int n,max,answer=0,arr[1005],dp[1005];
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&arr[i]);
		dp[i]=1;
		max=0;
		for(int k=0;k<i;k++){
			if(arr[k]<arr[i]){
				if(max<dp[k])
					max=dp[k];
			}
		}
		dp[i]=max+1;
	
		if(answer<dp[i])
			answer=dp[i];

	}
	printf("%d",answer);
	return 0;
}

 

쉬운 문젠데 왜 아이디어가 안 떠올랐지 쓰읍