Занятие 4. Справочник

Занятие 4. Справочник

int[] d = new int [MAXN]; //MAXN - наибольшее возможное значение n
for (int i=0; i < n; ++i)
{
        d[i] = 1; 
        for (int j=0; j < i; ++j)
                if (a[j] < a[i])
                        d[i] = Math.max (d[i], 1 + d[j]);
}
int ans = d[0];
for (int i=0; i < n; ++i)
        ans = Math.max (ans, d[i]);

Вывод ответа – наибольшей (наидлиннейшей) возрастающей подпоследовательности

int[] d = new int[MAXN]; // MAXN - наибольшее возможное значение n
int[] p = new int[MAXN]; // массив предков
for (int i = 0; i < n; ++i)
{
	d[i] = 1;
	//сначала предок отсутствует
	p[i] = -1;
	for (int j = 0; j < i; ++j)
		if (a[j] < a[i] && d[i] < d[j] + 1)
		{
			d[i] = d[j] + 1;
			//устанавливаем предка для i-го элемента
			p[i] = j;
		}
}
//индекс ПОСЛЕДНЕГО элемента НВП
int ians = 0;

for (int i = 1; i < n; ++i)
	if (d[ians] < d[i]) ians = i;

//Формируем путь
int i = ians;
int k = 0;
while(i != -1)
{
	way[k] = a[i];
	i = p[i];
	k++;
}	

//Выводим путь в обратном порядке
k--;
while(k >= 0)
{
	out.print(way[k] + " ");
	k--;
}