задача на динамическое программирование
Большое спасибо))
Цитата: Римма
Надо разработать алгоритм, находящий наибольшую возрастающую подпоследовательность данной последовательности из n чисел. Допускается, чтобы алгоритм работал за время порядка n^2 (но желательно за n*logn);)
Большое спасибо))
Вы сами пытались что-либо сделать? Язык нужно угадывать?
я пыталась, только не работает. вот код
program Project2;
{$APPTYPE CONSOLE}
uses
SysUtils;
const n=3;
var i,k,n1,j,s:integer; //k-максимальная длина возрастающей
//подпоследовательности
x,u : array [1..n] of integer; //u - минимальный из последних членов
//возрастающих подпоследовательностей длины i
begin
for i:=1 to n do
readln(x);
n1 := 1; k := 1; u[1] := x[1];
while n1 <> n do
begin
n1 := n1 + 1;
//////// поиск
i:=0; j:=k+1;
{u < x[n1] <= u[j], j > i}
while (j - i) <> 1 do
begin
s := i + (j-i) div 2; {i < s < j}
if u
else {u
i := s;
end; {u < x[n1] <= u[j], j-i = 1}
{i - наибольшее из тех чисел отрезка 1..k, для кото-
рых u < x[n1]; если таких нет, то i=0 }
///////////
if i = k then
begin
k := k + 1;
u[k+1] := x[n1];
end
else {i < k, u < x[n1] <= u[i+1] }
u[i+1] := x[n1];
end;
for i:=1 to n do
writeln (u);
readln;
end.