11053 가장 긴 증가하는 부분 수열

이 문제는 가장 긴 증가하는 or 감소하는 부분 수열 문제로 시리즈가 여러개 존재한다.

그만큼 우리가 확인해야하는 규칙성이 있다는 것인데,

알고리즘으로 LIS 알고리즘 (Longest Increase Sequence) 라고 한다.

11053 번 문제의 경우 N의 범위가 크지 않아 O(N^2) 으로 구현 가능하지만,

불가능한 경우 O(NlogN) 방식으로 구할 수 있다.

우선 이 문제는 완전탐색의 경우, 즉 O(N^2) 으로 풀이해두었다.

<소스코드>

#include <cstdio>

int N, A[1001], dp[1001], minn, maxx;

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) scanf("%d", A + i);
	for (int i = 1; i <= N; i++) {
		minn = 0;
		for (int j = 0; j < i; j++) {
			if (A[i] > A[j]) {
				if (minn < dp[j]) minn = dp[j];
			}
		}
		dp[i] = minn + 1;
		if (maxx < dp[i]) maxx = dp[i];
	}
	printf("%d\n", maxx);
	return 0;
}