11568 - 민균이의 계략

최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 로 해결할 수 있다.

이 문제는 $O(N^2)$ 도 가능하다. 현재 자신보다 이전에 더 작은 수가 있다면, 현재값과 그 수까지의 LIS+1 중에 더 큰 값으로 선택하면 된다.

코드로 구현하면 아래와 같다.

int answer = 0;
for(i=0; i<n; ++i){
    for(j=i; j>=0; --j){
        if(a[j] < a[i]){
            LIS[i] = max(LIS[i], LIS[j]+1);
        }
    }
    answer = max(LIS[i], answer);
}
printf("%d", answer+1);