Матч 388, Монотонная последовательность (MonotoneSequence)

Дивизион 2, Уровень 1

Строго возрастающей называется последовательность, каждый элемент которой строго больше предыдущего элемента. Строго убывающей называется последовательность, каждый элемент которой строго меньше предыдущего элемента. Последовательность называется строго монотонной, если она или строго возрастающая, или строго убывающая.

В последовательности seq следует найти длину самой длинной строго монотонной подпоследовательности.

Класс: MonotoneSequence

Метод: int longestMonotoneSequence(vector<int> seq)

Ограничения: seq содержит от 1 до 50 чисел в промежутке от 1 до 100.

Вход. Массив целых чисел seq.

Выход. Длина самой длинной строго монотонной подпоследовательности.

Пример входа

seq

{1, 7, 7, 8, 3, 6, 7, 2}

{10, 20, 30, 25, 20, 19, 20, 18, 23}

{3, 2, 1, 4}

Пример выхода

3

4

3

РЕШЕНИЕ

обработка последовательности

Задача решается за линейное время. Последовательно проходим по элементам массива. В переменной s храним длину текущего монотонного куска последовательности. Переменная max хранит длину самой длинной строго монотонной подпоследовательности. Функция monotone находит длину самой длинной строго возрастающей подпоследовательности: если текущий элемент seq[i] больше предыдущего seq[i – 1], то увеличиваем длину текущей возрастающей подпоследовательности s на 1, иначе проверяем, не больше ли s значения max, и устанавливаем s равным 1.

Сначала запускаем функцию monotone на последовательности seq, находим длину самой длинной строго возрастающей подпоследовательности. Затем обращаем последовательность seq и снова запускаем функцию monotone. Таким образом находим длину самой длинной строго убывающей подпоследовательности. Возвращаем максимум среди значений, возвращаемых функцией monotone в первый и во второй раз.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

int monotone(vector<int> seq)

{

int i, max, s;

for(max = s = 1, i = 1; i < seq.size(); i++)

{

if (seq[i] > seq[i-1]) s++;

else

{

if (s > max) max = s;

s = 1;

}

}

if (s > max) max = s;

return max;

}

class MonotoneSequence

{

public:

int longestMonotoneSequence(vector<int> seq)

{

int temp, res = monotone(seq);

reverse(seq.begin(),seq.end());

temp = monotone(seq);

if (temp > res) res = temp;

return res;

}

};