// pd1.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <vector>
#include <iostream>

using namespace std;

vector<int> subsir(int* v, int n)
{
	int* sir;
	int ok = 0;

	sir = new int[n];

	for (int i = 0; i < n; i++)
	{
		sir[i] = 1;

		for (int k = i - 1; k >= 0; k--)
		{
			if (v[k] < v[i] && sir[i] < sir[k] + 1)
			{
				sir[i] = sir[k] + 1;
			}
		}
	}

	vector<int> ret;
	int max = 1;
	int add;

	for (int i = 0; i < n; i++)
	{
		if (sir[i] == max)
			add = v[i];
		else
			if (sir[i] == max + 1)
			{
				ret.push_back(add);
				add = v[i];
				max++;
			}
	}
	ret.push_back(add);

	delete [] sir;
	return ret;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int v[] = {1, 2, 3, 2, 7, 6, 8, 6, 7, 9};
	vector<int> sir = subsir(v, 10);

	for (vector<int>::iterator it = sir.begin(); it != sir.end(); it++)
		cout << *(it) << " ";
	cout << endl;

	return 0;
}