[코드업] 3735 - LIS (Small)

LIS(Longest Increasing subsequence)란 최장 증가 부분수열을 말한다.

프로그래밍 문제를 풀 다 보면 이것을 응용하는 문제가 많이 출제되고 있고, 동적계획법의 대표적인 사용 예 중 하나이다.

다음과 같은 원소의 개수가 8개(N)인 수열이 있을 때,

1 3 2 9 7 8 5 10 

LIS = 1 2 7 8 10 으로 그 길이는 5이다.

입력 예시  

8
1 3 2 9 7 8 5 10

출력 예시

5

#include<iostream>
#include<algorithm>
using namespace std;

int N;
int arr[1001];
int dp[1001];

int search(int pos) { // pos에서 시작해서 최대길이
	int& ret = dp[pos];
	if (ret != 0) return ret;

	ret = 1;
	for (int next = pos + 1; next < N; next++) {
		if (arr[pos] < arr[next])
			ret = max(ret, search(next) + 1);
	}

	return ret;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	int maxVal = -987654321;
	for (int begin = 0; begin < N; begin++)
		maxVal = max(maxVal, search(begin));

	cout << maxVal;

	return 0;
}