풀이전략

• LIS
• 역으로 추적하자.

소스코드

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



//위에서 부터 나오게 하자. 
int main(void)
{
	int n;
	cin >> n;

	vector<int >v(n);
	vector<int>dp(n, 1);

	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}

	dp[0] = 1;

	for (int i = 1; i < n; i++)
	{
		for (int j = i - 1; j >= 0; j--)
		{
			if (v[j] < v[i])
			{
				dp[i] = max(dp[j] + 1, dp[i]);
			}
		}
	}

	int max_Value = -1;
	for (int i = 0; i < n; i++)
	{
		max_Value = max(dp[i], max_Value);
	}

	cout << max_Value << "\n";
	
	vector<int>result;
	for (int i = dp.size() - 1; i >= 0; i--)
	{
		if (max_Value == dp[i])
		{
			max_Value--;
			result.push_back(v[i]);
		}
	}

	reverse(result.begin(), result.end());
	for (int i = 0; i < result.size(); i++)
		cout << result[i] << " ";
}