// най-дълга растяща подредица на масив за O(n^2)
// на реда, отбелязан с *, ако заменим a[i] > a[j] с a[i] >= a[j] получаваме най-дълга сортирана подредица

#include <iostream>
using namespace std;

const int n = 10;

int parent[n];
int memo[n];
int num = 1;
int indx = 0;

int a[n] = { 5, 3, -1, 2, 6, 17, 4, 8, 9, -2 };

void show_seq(int i)
{
	if (i != -1){ show_seq(parent[i]); cout << a[i] << " "; }
}

int main()
{
	memo[0] = 1;
	parent[0] = -1;

	for (int i = 1; i < n; i++)
	{
		int m = 0;
		parent[i] = -1;

		for (int j = 0; j < i; j++) if (a[i] > a[j] && memo[j] > m) //*
		{
			m = memo[j];
			parent[i] = j;
		}

		memo[i] = m + 1;

		if (memo[i] > num)
		{
			num = memo[i];
			indx = i;
		}
	}

	cout << num << endl;

	show_seq(indx);

	cout << endl;

	return 0;
}