Максимальная длина монотонного фрагмента последовательности.
дана последовательность натуральных чисел, завершающаяся числом 0. определите наибольшую длину монотонного фрагмента последовательности (то есть такого фрагмента, где все элементы либо больше предыдущего, либо меньше).
ввод вывод
1 2
7
7
9
1
0
===== PascalABC.NET =====
begin
var (k, kmax, s) := (1, 0, 1);
var a := ReadInteger;
if a = 0 then
begin
Print(1);
exit
end;
foreach var b in ReadSeqIntegerWhile(p -> p <> 0) do
begin
var sgn := Sign(b - a);
a := b;
if sgn = s then
k += 1
else
begin
if k > kmax then
kmax := k;
(k, s) := (2, sgn)
end
end;
if k > kmax then
kmax := k;
Print(kmax)
end.
Чтобы решить эту задачу, нам необходимо проанализировать последовательность в поисках монотонных фрагментов.
Давайте рассмотрим каждый шаг по порядку:
1. Мы начинаем с первого числа в последовательности. Зафиксируем его и будем считать текущую длину монотонного фрагмента равной 1.
2. Далее переходим к следующему числу. Если оно больше предыдущего числа, то оно продолжает монотонный фрагмент, и мы увеличиваем длину монотонного фрагмента на 1.
3. Если же текущее число меньше предыдущего числа, то монотонный фрагмент заканчивается. Мы записываем текущую длину монотонного фрагмента и обнуляем ее, чтобы начать подсчет нового монотонного фрагмента.
4. Продолжаем шаги 2-3 для всех последующих чисел в последовательности, пока не достигнем числа 0, которое служит указателем конца последовательности.
5. В конце подсчета мы выбираем наибольшую длину монотонного фрагмента и выводим ее как ответ на задачу.
Теперь рассмотрим пример, чтобы проиллюстрировать наше решение:
Последовательность: 1 2 7 7 9 1 0
Шаг 1: 1 - начинаем считать длину монотонного фрагмента равную 1.
Шаг 2: 2 - число больше предыдущего, продолжаем монотонный фрагмент, длина становится 2.
Шаг 3: 7 - число больше предыдущего, продолжаем монотонный фрагмент, длина становится 3.
Шаг 4: 7 - число равное предыдущему, продолжаем монотонный фрагмент, длина остается 3.
Шаг 5: 9 - число больше предыдущего, продолжаем монотонный фрагмент, длина становится 4.
Шаг 6: 1 - число меньше предыдущего, монотонный фрагмент заканчивается с длиной 4. Продолжим поиск нового монотонного фрагмента с длиной 1.
Шаг 7: 0 - указатель конца последовательности, заканчиваем подсчет.
Наибольшая длина монотонного фрагмента в данном случае равна 4.
Ответ: 4.
Дорогой ученик, я надеюсь эта подробная демонстрация и пошаговое решение помогли вам лучше понять, как решить данную задачу.