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

Задача

Заполнить массив случайными числами, вывести его на экран. Найти самую длинную последовательность чисел, упорядоченную по возрастанию. Вывести ее на экран. Если таких последовательностей несколько (самых длинных с одинаковой длиной), то вывести их все.

Решение

Описание переменных: 

  • i - индекс текущего элемента массива;
  • l - длина текущей последовательности, упорядоченной по возрастанию;
  • lmax - длина самой длинной последовательности, упорядоченной по возрастанию;
  • j - индекс текущего элемента выводимой на данный момент последовательности.

Алгоритм решения задачи: 

Задачу можно разбить на три подзадачи:

  1. Заполнение и вывод массива.
  2. Определение длины самой длинной последовательности чисел, упорядоченных по возрастанию.
  3. Вывод всех упорядоченных по возрастанию последовательностей с найденной в п. 2 длинной.

Алгоритм определения длины:

  1. Присвоить переменным lmax и l значение 1.
  2. В цикле перебирать элементы массива, начиная со второго:
    1. если очередной элемент больше предыдущего, то увеличивать на 1 значение l;
    2. иначе:
      1. если l больше lmax, то присвоить lmax значение l,
      2. снова присвоить l единицу.

Вывод всех самых длинных последовательностей, упорядоченных по возрастанию:

  1. Снова просматриваем массив и находим длину текущей последовательности, упорядоченной по возрастанию.
  2. Если эта длина равна lmax, то выводим элементы массива, начиная с i-l до i-1 (с начала последовательности до предыдущего элемента).

Программа на языке Паскаль: 

 

const N = 45;
var
    arr: array[1..N] of byte;
    i, j, l, lmax: byte;
begin
    randomize;
    for i:=1 to N do begin
        arr[i] := random(100);
        write(arr[i]:3);
    end;
    writeln;
 
    lmax := 1;
    l := 1;
    for i:=2 to N do 
        if arr[i] > arr[i-1] then
            l := l + 1
        else begin
            if l > lmax then
                lmax := l;
            l := 1;
        end;
    writeln(lmax);
    if lmax = 1 then exit;
 
    l := 1;
    for i:=2 to N do 
        if arr[i] > arr[i-1] then
            l := l + 1
        else begin
            if l = lmax then begin
                for j:=i-l to i-1 do
                    write(arr[j]:3);
                writeln;
            end;
            l := 1;
        end;
end.

 

Пример выполнения программы:

 62  6 11  2 78 37 99  8 80  3 59 71 85 59 46 66  1 43 89 67 48 72 88 57 82 62 51 14  6 88 47 79 96 98 97 58 50 60 58 84 98 69  2 46 12
4
  3 59 71 85
 47 79 96 98

 

Тема

Одномерные массивы

Уровень

Комбинированные задачи

Комментарии

Гость 15/01/2016

Неверное решение! Второй цикл работает верно, если только наибольшая последовательность не находится в конце. К примеру если взять последовательность {1,2,3,4,5,3,2,5,7,9,10,11}, то явно максимальная последовательность будет состоять из 6 элементов, однако, дойдя до последнего элемента l=6, но в else цикл не перейдет, т.к. не выполнится условие arr[i] > arr[i-1], потому что последний элемент сравнить не с чем. Тут нужно еще условие на проверку конца цикла....

Гость 18/02/2016 
const n=20;
var a: array[1..n] of integer;
    max, i, l, i2: integer;
begin
writeln('Последовательность чисел:');
for i:=1 to n do
begin
a[i]:= random(100);
write(a[i]:3);
end;
writeln;
l:=1;
for i:=2 to n do
begin
if a[i]>a[i-1] then
l:=l+1;
if (a[i]<=a[i-1]) or (i=n) then
begin
if l>max then
max:=l;
l:=1;
end;
end;
writeln('max=', max);
if max=1 then exit;
for i:=2 to n do
begin
 if a[i]>a[i-1] then
 l:=l+1;
 if (a[i]<=a[i-1]) or (i=n) then
 begin
  if max=l then
   if (i=n)and(a[i]>a[i-1]) then
   for i2:=i-l+1 to i do
   write(a[i2]:3)
   else
   for i2:=i-l to i-1 do
   write(a[i2]:3);
   writeln;
   l:=1;
 end;
end;
end.