가장 긴 증가하는 부분 수열 (백준 - 11053번)

 

동적 계획법을 사용하는 문제였다.

 

가장 긴 증가하는 부분 수열은 LIS라고 하며 이전에 자세하게 언급한 적이 있으므로 해당 게시글을 참조하길 바란다.

https://lipcoder.tistory.com/50?category=843242

최장증가수열 - LIS(Longest Increasing Subsequence)

하지만 위와 다른 점이 있다면 위 문제의 경우는 중복되는 숫자가 있다는 점이다. 그것을 감안하고 풀면 되겠다.

 

코드는 다음과 같다.

#include <iostream>
#include <string.h>
using namespace std;

int main()
{
	int input;
	cin >> input;

	int* dp = new int[input + 1];
	int* num = new int[input + 1];
	memset(dp, 0, sizeof(int) * (input + 1));
	memset(num, 0, sizeof(int) * (input + 1));
	for (int i = 1; i <= input; ++i)
	{
		cin >> num[i];
	}

	int result = 0;
	for (int i = 1; i <= input; ++i)
	{
		int max = 0;
		for (int j = 0; j < i; ++j)
		{
			if (num[i] > num[j])
			{
				if (max < dp[j])
					max = dp[j];	
			}
		}
		dp[i] = max + 1;
		if (dp[i] > result)
			result = dp[i];
	}
	cout << result << endl;

	delete[] dp;
	delete[] num;
}