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).
Definition
- Class:
- MonotoneSequence
- Method:
- longestMonotoneSequence
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int longestMonotoneSequence(int[] seq)
- (be sure your method is public)
Constraints
- seq will contain between 1 and 50 elements, inclusive.
- Each element of seq will be between 1 and 100, inclusive.
Examples
{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
{100, 100}
Returns: 1
{1, 100}
Returns: 2
{100, 1}
Returns: 2
{1, 2, 3}
Returns: 3
{3, 2, 1}
Returns: 3
{1, 2, 2}
Returns: 2
{2, 1, 2}
Returns: 2
{2, 1, 1}
Returns: 2
{1, 1, 2}
Returns: 2
{3, 2, 3, 4, 5, 5, 5, 4, 3, 2, 1, 1, 1}
Returns: 5
{100, 90, 80, 70, 60, 60, 50, 40, 30, 20, 10}
Returns: 6
{1, 2, 3, 4, 5, 6, 6, 7, 8, 9, 10, 11, 12, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
Returns: 12
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50}
Returns: 50
{50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
Returns: 50
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 1, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50}
Returns: 26
{1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2}
Returns: 2
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Returns: 1
{3, 2, 1, 4}
Returns: 3
{1, 2, 3, 4, 5, 6, 77}
Returns: 7
{12, 11, 10, 6}
Returns: 4
{1, 2, 3, 3}
Returns: 3
{4, 1, 6, 1, 7, 1, 2, 3, 4}
Returns: 4
{2, 2, 1, 1, 2, 3, 7, 3, 2, 1}
Returns: 4
{1 }
Returns: 1
{8, 7, 6, 5, 4 }
Returns: 5
{2, 1, 2, 3, 4 }
Returns: 4
{5 }
Returns: 1
{10, 20, 30, 25, 20, 19, 20, 18, 23 }
Returns: 4
{9 }
Returns: 1
{2 }
Returns: 1
{55 }
Returns: 1
{1, 2, 3, 4, 5 }
Returns: 5
{1, 100, 100, 99, 99, 98, 97, 96, 95, 94, 93, 92, 91 }
Returns: 9
{1, 2 }
Returns: 2
{1, 5, 9, 5, 1, 5, 9, 5, 1, 5, 9 }
Returns: 3
{1, 2, 2, 4 }
Returns: 2
{5, 4, 3, 2, 1 }
Returns: 5
{9, 8, 7, 6, 5 }
Returns: 5
{3, 2, 1, 4 }
Returns: 3
{1, 2, 1, 2, 3, 4 }
Returns: 4
{1, 5 }
Returns: 2
{1, 2, 3, 4 }
Returns: 4
{3, 2, 2, 1 }
Returns: 2
{1, 10, 9, 8, 5 }
Returns: 4
{3, 7, 10, 15, 26, 59 }
Returns: 6
{5, 4, 2, 3, 4, 5 }
Returns: 4
{3 }
Returns: 1
{3, 2, 1, 2, 3, 4, 5 }
Returns: 5
{1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2, 1 }
Returns: 3
{3, 4, 5 }
Returns: 3
{4, 5, 1, 1, 1, 2, 2, 1 }
Returns: 2
{1, 7, 7, 8, 3, 6, 6, 2 }
Returns: 2
{2, 2, 8, 9 }
Returns: 3