←  Динамическое программирование

олимпиадники-информатики

»

Максимальная подпоследовательность

Санек фотография Санек 23 дек 2011

Дана числовая последовательность, вывести длину максимальной возрастающей подпоследовательности.

Входные данные

В первой строке вводится n (1<=n<=1000) - длина последовательности. Далее идет сама последовательность длиной n чисел (все числа по модуля не превосходят 10000).

Выходные данные

Одно число - ответ на задачу.

Решение

var a,f:array [1..10000]of longint;
	n,i,max,j:longint;
begin
readln(n); //читаем кол-во чисел
for i:=1 to n do
  read(a[i]); //считываем последовательность
for i:=1 to n do
  f[i]:=1; //забиваем массив ответов 1
for i:=1 to n do
  for j:=1 to i-1 do
   if (a[i]>a[j]) and (f[j]+1>f[i]) then f[i]:=f[j]+1; //ищем длину возрастающей последовательности на каждом шаге последовательности
for i:=1 to n do
  if f[i]>max then max:=f[i]; //находим максимальную подпоследовательность в массиве ответов
writeln(max);
end.
Ответить