Задача на динамическое программирование

[Римма]

Разработать алгоритм, находящий наибольшую возрастающую подпоследовательность данной последовательности из n чисел. Допускается, чтобы алгоритм работал за время порядка n^2 (но желательно за n*logn).

Большое спасибо!!!

[Naeel Maqsudov]

Код: Выделить всё

const
  n=25;
  m=(n+1) div 2;
  seq:array[1..n] of integer = (
    3,5,2,1,3,23,4,34,34,54,4,54,56,46,3,6,3456,345,63,456,4,56,45,4,6
  );
  
var
  i,maxlen,seqi:integer;
  pos:array[1..m] of integer;
  len:array[1..m] of integer;
begin
  for i:=1 to m do begin pos[i]:=-1; len[i]:=1; end;
  seqi:=1;
  
  for i:=1 to pred(25) do begin
    if seq[i]<seq[succ(i)] then begin
      if pos[seqi]=-1 then pos[seqi]:=i;
      inc(len[seqi]);
    end else begin
      if pos[seqi]>=0 then inc(seqi);
    end
  end;
  maxlen:=1;
  for i:=2 to seqi do if len[i]>len[maxlen] then maxlen:=i;
  
  writeln('самая длинная последовательность начинается с позиции ',
    pos[maxlen],' и имеет длину ', len[maxlen])
end.

[Римма]

спасибо. но только вы не правильно меня поняли((
из последовательности например 1 3 17 4 19 30 2 90
должен быть ответ 1 3 17 19 30 90, т.к. там не сказано чтобы была последовательность по порядку
и за какое время она проходит: n^2 или n*logn?

[Esgal]

вы уверенны в том что вас неправильно поняли?

[Римма]

да, уверена. я у преподавателя спрашивала

[Z-Creed]

Код: Выделить всё

const
  n=25;
  m=(n+1) div 2;
  seq:array[1..n] of integer = (
    3,5,2,1,3,23,4,34,34,54,4,54,56,46,3,6,3456,345,63,456,4,56,45,4,6
  );
  
var
  i,maxlen,seqi:integer;
  pos:array[1..m] of integer;
  len:array[1..m] of integer;
begin
  for i:=1 to m do begin pos[i]:=-1; len[i]:=1; end;
  seqi:=1;
  
  for i:=1 to pred(25) do begin
    if seq[i]<seq[succ(i)] then begin
      if pos[seqi]=-1 then pos[seqi]:=i;
      inc(len[seqi]);
    end else begin
      if pos[seqi]>=0 then inc(seqi);
    end
  end;
  maxlen:=1;
  for i:=2 to seqi do if len[i]>len[maxlen] then maxlen:=i;
  
  writeln('самая длинная последовательность начинается с позиции ',
    pos[maxlen],' и имеет длину ', len[maxlen])
end.

А можете решить математическим методом(условие, решение)?