Непрерывная неубывающая последовательность чисел (TurboPascal)

[VladKB1]

В наборе чисел найдите непрерывную неубывающую последовательность чисел
максимальной длины. Если подходящих последовательностей несколько, выведите первую из
них. -maxint ≤ a ≤ maxint.

Формат ввода: первая строка: n ≤ 300 000. Вторая строка: элементы набора чисел.
Формат вывода: искомая последовательность.

input.txt
7
5 1 2 3 4 3 7

output.txt
1 2 3 4

[SlavaSSU]

а у тебя есть какие-нибудь мысли? или вообще не представляешь, как это решать?

[VladKB1]

Сообщение от SlavaSSU

а у тебя есть какие-нибудь мысли? или вообще не представляешь, как это решать?

Решить смогу , но по времени не пройдёт 1 тест-1 секунда.

Скоро выложу код.

[SlavaSSU]

эту задачу надо решать жадно. т.е. пусть мы уже что-то набрали и стоим в индексе idx, тогда если a[idx + 1] >= a[idx], т.е. мы можем еще добавить в конец один эдемент, то нам никогда не выгодно его не добавлять, поэтому добавим его в конец. если же неубываемость нарушается, то нам нет смысла смотреть на предыдущие элементы, т.е. надо начинать новую последовательность

[VladKB1]

Сообщение от SlavaSSU

эту задачу надо решать жадно. т.е. пусть мы уже что-то набрали и стоим в индексе idx, тогда если a[idx + 1] >= a[idx], т.е. мы можем еще добавить в конец один эдемент, то нам никогда не выгодно его не добавлять, поэтому добавим его в конец. если же неубываемость нарушается, то нам нет смысла смотреть на предыдущие элементы, т.е. надо начинать новую последовательность

Спасибо за совет но я пытался, пытался не получается. Можете расписать алгоритм действий?

[SlavaSSU]

l := 1; //1-ая нерассмотренаая ячейка
r := 1;
anslen := 0;
ansl := 0;
ansr := 0;
while(l <= n) do begin
r := l;
//начиная с этой позиции идем вправо пока можем
while(r + 1 <= n && a[r + 1] >= a[r]) do
inc(r);
// пробуем обновить ответ
if(r - l + 1 > anslen) then begin
anslen := r - l + 1;
ansl := l;
ansr := r;
end;

//последняя рассмотренная позиция была r, поэтому новая ерассмотренная поцизия r + 1;
l := r + 1;
end;

// теперь в ansl и ansr хранятся индексы ответа

[VladKB1]

Сообщение от SlavaSSU

l := 1; //1-ая нерассмотренаая ячейка
r := 1;
anslen := 0;
ansl := 0;
ansr := 0;
while(l <= n) do begin
r := l;
//начиная с этой позиции идем вправо пока можем
while(r + 1 <= n && a[r + 1] >= a[r]) do
inc(r);
// пробуем обновить ответ
if(r - l + 1 > anslen) then begin
anslen := r - l + 1;
ansl := l;
ansr := r;
end;

//последняя рассмотренная позиция была r, поэтому новая ерассмотренная поцизия r + 1;
l := r + 1;
end;

// теперь в ansl и ansr хранятся индексы ответа

Большое спасибо! а что это значит && ?

[SlavaSSU]

лол. я на паскале давно не писал! это логическое и.
в с++ &&
в паскале and

[VladKB1]

Сообщение от SlavaSSU

лол. я на паскале давно не писал! это логическое и.
в с++ &&
в паскале and

понятно ))

[VladKB1]

Ну вроде бы готово только индексы у меня 6 и 7 ((

var
 n,i,l,r,z,x,c: longint;
 a: array [1..1000] of longint;
begin
 assign(input,'input.txt');
 reset(input);
 assign(output,'output.txt');
 rewrite(output);

 read(n);
 for i:=1 to n do read(a[i]);

 l:=1;
 r:=1;
 while (l <= n) do
 begin
  r:=l;
  while (r+1 <= n) and (a[r+1] >= a[r]) do inc(r);
  if (r-l+1 > z) then
  begin
   x:=l;
   c:=r;
  end;
  l:=r+1;
 end;
 for i:=x to r do write(a[i],' ');
end.