[C++] 최대 부분 증가수열 🔥

📄문제

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가수열을 만들 수 있다.

 

⬇️ 입력

첫째 줄은 입력되는 데이터의 수 N(1≤N≤1,000, 자연수)를 의미하고,
둘째 줄은 N개의 입력데이터들이 주어진다.

8 5 3 7 8 6 2 9 4

 

⬆️ 출력

첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

4

 

📝 풀이

#include <iostream>
using namespace std;

int dp[1001];
int numbers[1001];

int main()
{
	int N, ans = INT_MIN;;
	cin >> N;

	for (int i = 0; i < N; ++i)
		cin >> numbers[i];

	dp[0] = 1;

	for (int i = 1; i < N; ++i)
	{
		int max = 0;

		for (int j = i - 1; j >= 0; --j)
		{
			// 뒤 숫자가 더 큰경우 갱신
			if (numbers[j] < numbers[i])
			{
				if (max < dp[j])
				{
					max = dp[j];
				}
			}

			dp[i] = max + 1;
		}

		if (ans < dp[i])
			ans = dp[i];
	}

	cout << ans;
}

 

• "가장 긴 증가하는 부분 수열"을 구하는 프로그램입니다. 이 알고리즘은 동적 프로그래밍을 사용하여 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾습니다. 
• 입력받은 숫자를 차례대로 검사하여 numbers[j]가 numbers[i]보다 작으면, numbers[j]에 저장되어 있는 최대 수열의 길이보다 1 더 길어지게 저장할 수 있습니다.
• 예를들어 1, 2, 4, 3 수열이 있을 때 i가 3, j가 4로 보았을 때 j는 4보다 크기때문에 갱신될 수 없습니다.
• 반대로, j가 2일때는 i보다 더 작기때문에, 2까지 누적된 수열의 길이 + 1을 하여 dp[i]에는 3이 저장됩니다.