Задание № 7515
Пусть дана последовательность А целых чисел, пронумерованных от 1 до N. Будем называть невозрастающей подпоследовательностью подряд идущие элементы последовательности, такие, что Аi ⩾ Аi + 1 ⩾ ... ⩾ Ak - 1 ⩾ Ak, (k > i > 0). Длиной подпоследовательности будем называть количество входящих в неё элементов. Любой отдельно взятый элемент представляет собой невозрастающую подпоследовательность длины 1. От цифровых датчиков в компьютер поступает информация о характеристиках физического процесса. Результатом каждого измерения является целое число.
Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет искать максимальную длину невозрастающей подпоследовательности.
Следует учитывать, что количество измерений может быть очень велико.
Перед текстом программы кратко опишите используемый вами алгоритм решения задачи. На вход программе в первой строке подаётся общее количество N значений измерений. В каждой из последующих N строк записано целое число. Гарантируется, что N ⩾ 1, то есть всегда имеется хотя бы одно значение измерений.
<!—QuoteBegin—>Пример входных данных:
5
-1000
0
-300
2
2000
<!—QuoteEnd—>Результатом работы программы должно являться целое число — максимальная длина невозрастающей подпоследовательности.
Пример выходных данных для приведённого выше примера входных данных:
2
Содержание верного ответа
Программа читает значения измерений, обновляя при необходимости текущую максимальную длину искомой последовательности. Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая. Ниже приведёны примеры решения задания на языках Паскаль, Бейсик и алгоритмическом языке. Допускаются решения, записанные на других языках программирования
Пример правильной и эффективной программы на языке Бейсик
DIM N, cnt, i, t, prev, Max AS INTEGER Max = 1 cnt = 1 INPUT NREM Считали количество измерений FOR i = 1 TO N INPUT tREM Считали очередное значение IF i = 1 THEN prev = t ELSE IF prev >= t THEN cnt = cnt + 1 ELSE IF cnt > Max THEN Max = cntREM Обновление максимальной длины cnt = 1 END IF END IF prev = t END IF NEXT iIF cnt > Max THEN Max = cntREM Обработка «хвоста» последовательности END IFPRINT MaxПример правильной и эффективной программы на языке Паскаль
var N, cnt, i, t, prev, Max: integer; begin Max := 1; cnt := 1; ReadLn(N); {Считываем количество измерений} for i := 1 to N do begin ReadLn(t); {Считали очередное значение} if i = 1 then prev := t else if prev >= t then cnt := cnt + 1 else begin if cnt > Max then Max := cnt; {Обновление максимальной длины} cnt := 1; end; prev := t; end; if cnt > Max then Max := cnt; {Обработка «хвоста» последовательности} WriteLn (Max); end.Нашли ошибку в задании? Выделите фрагмент и нажмите Ctrl + Enter.