Перейти к содержимому


- - - - -

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


В этой теме нет ответов

#1 Санек

    Продвинутый пользователь

  • Администраторы
  • 37 сообщений
  • ГородВитебск

Отправлено 23 декабря 2011 - 19:10

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

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

В первой строке вводится 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.






Количество пользователей, читающих эту тему: 1

0 пользователей, 1 гостей, 0 анононимных