MonotoneSequence
SRM 388 · 2008-01-15 · by bmerry
Problem Statement
A strictly increasing sequence is a sequence of numbers where each number is strictly greater than the previous one. A strictly decreasing sequence is a sequence where each number is strictly less than the previous one. A strictly monotone sequence is a sequence that is either strictly increasing or strictly decreasing. For example, 1, 5, 6, 10 and 9, 8, 7, 1, are strictly monotone sequences, while 1, 5, 2, 6 and 1, 2, 2, 3 are not.
Given a sequence seq, determine the length of the longest contiguous subsequence that is strictly monotone (see examples for clarifications).
Constraints
- seq will contain between 1 and 50 elements, inclusive.
- Each element of seq will be between 1 and 100, inclusive.
{1, 7, 7, 8, 3, 6, 7, 2}
Returns: 3
The longest contiguous monotone subsequence is 3, 6, 7. The sequence 1, 3, 6, 7 is not valid because 1 and 3 are not adjacent, and 1, 7, 7, 8 is not valid because it is not strictly increasing.
{1, 1, 1, 1, 1}
Returns: 1
A sequence of one element is valid.
{10, 20, 30, 25, 20, 19, 20, 18, 23}
Returns: 4
{1}
Returns: 1
{100}
Returns: 1
Submissions are judged against all 58 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MonotoneSequence with a public method int longestMonotoneSequence(vector<int> seq) · 58 test cases · 2 s / 256 MB per case