[백준] 11053번: 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

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

 

난이도: solved.ac 실버 2

 

LIS(Longest Increasing Subsequence)문제다.

나는 DP를 이용해 풀었다.

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAXLEN 1000
#define max(a,b) ((a)>(b)?(a):(b))

int main() {
	int A[MAXLEN];
	int length[MAXLEN];
	int N, i, j;
	
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%d", &A[i]);
	for (i = 0; i < N; i++) {
		length[i] = 1;
		for (j = 0; j < i; j++) {
			if (A[i] > A[j])
				length[i] = max(length[i], length[j] + 1);
		}
	}
	int max_len = 0;
	for (i = 0; i < N; i++) {
		if (length[i] > max_len)
			max_len = length[i];
	}
	printf("%d", max_len);
	return 0;
}