#include<bits/stdc++.h>
using namespace std;
#define mine
int a[1001];
int cache[1001];
int N;
int incSeq(int start){
if(start > N) return 0;
int& ret = cache[start];
if(ret != -1) return ret;
ret = 1;
for(int i=start+1; i<=N; i++){
if(a[start] < a[i]){
//start에서 갈 수 있는 수열중 제일 긴 길이를 찾는 것이다.
ret = max(ret, incSeq(i)+1);
}
}
return ret;
}
int main(){
ios_base::sync_with_stdio(false);
freopen("../input.txt","rt",stdin);
memset(cache, -1, sizeof(cache));
cin >> N;
for(int i=1; i<=N; i++){
cin >> a[i];
}
int res = 0;
for(int i=1; i<=N; i++){
res = max(incSeq(i), res);
}
cout << res << endl;
return 0;
}
자기보다 긴 값이 생길때마다 재귀를 돌려서 다시 그 값을 기준으로 반복하는 아이디어 기억하자.