#include <iostream> #include <vector> using namespace std; int v[1001]; int d[1001]; int main() { int n; cin>>n; for (int i=0;i< n ; i++) { int in; cin>>in; v[i]=in; } for(int i=0;i<n;i++) { d[i]=1; for(int j=0;j<i;j++) { if(v[j]<v[i] && d[j]+1 > d[i]) { d[i]=d[j]+1; } } } int max=0; for(int i=0;i<n;i++) { if(max<d[i]) max=d[i]; } cout<<max; return 0; }
각 숫자마다 순열의 길이를 d[i] 저장해주고, d[i]는 그 i번째 숫자가 앞에숫자보다 크고, 순열의 길이가 가장긴 값에 +1 을 해서 더해주었다