14002. 가장 긴 증가 4.

중요!

역추적해야 한다.

• 반드시 이렇게 해야 한다.
  

• 이렇게 하면 중간에 동일한 값을 가지고 있는 것들에서 걸린다.
  

#include <vector>
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <unordered_map>
#include <filesystem>
using namespace std;

#include <limits.h>


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	
	// 10 20 10 10 10 30 20 50 
	// 1  2  1  1  1  3 

	// 타겟 인덱스를 기준으로 해서 바로 인접한
	// 거에서부터 0지점까지 나아가면서 카운팅하자. 

	// 5 6 1 2 3 7 1 10 2
	// 1 2 1 2 3 4 1 5  2 
	// -> 모든 memo 중에서 가장 큰거를 출력하자. 

	// 


	int n;
	cin >> n;

	vector<int> v(n);
	vector<int> memo(n, 1);
	vector<int> rev(n, 1);

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

	// 이미 해당 value는 v에 있다. 

	// i 는 타겟팅이고, 
	for (int i = 0; i < n; ++i)
	{
		for (int j = i; j >= 0; --j)
		{
			if (v[j] < v[i] && memo[i] < memo[j] + 1)
			{
				memo[i] = memo[j] + 1;
				rev[i] = j;
			}
		}
	}

	int maxx = *max_element(memo.begin(), memo.end());

	//for (auto& iter : rev)
	//{
	//	cout << iter << endl;
	//}

	vector<int> res;
	
	for (int i = memo.size() - 1; i >= 0; --i)
	{
		if (maxx == memo[i])
		{
			res.push_back(v[i]);
			maxx--;
		}
	}
	
	
	for (auto& iter : res)
		cout << iter << endl;
}