[BOJ 14002] 가장 긴 증가하는 부분 수열 4

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

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

---

[BOJ 11053] 가장 긴 증가하는 부분 수열 과 똑같이 길이를 구한 뒤에 dp의 맨 끝부터 탐색을 하면서 가능한 최대 길이랑 같은지 다른지를 확인하면 된다.

같은 값이 나올 때마다 최대 길이를 1씩 줄여서 dp[i]에서 가능한 최대 길이를 구하면 된다.

---

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

using namespace std;

int n;
int a[1001];
int dp[1001];

int main()
{
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%d", a + i);
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		dp[i] = 1;
		for (int j = i - 1; j >= 1; j--)
		{
			if (a[i] > a[j])
				dp[i] = max(dp[i], dp[j] + 1);
		}
		ans = max(ans, dp[i]);
	}

	printf("%d\n", ans);

	stack<int> s;
	for (int i = n; i > 0; i--)
		if (dp[i] == ans)
			s.push(a[i]), ans--;

	while (!s.empty())
		printf("%d ", s.top()), s.pop();
}