ZigZag
TCCC '03 Semifinals 3 · 2003-04-04 · by vorthys
Problem Statement
A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.
For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.
Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.
Constraints
- sequence contains between 1 and 50 elements, inclusive.
- Each element of sequence is between 1 and 1000, inclusive.
{ 1, 7, 4, 9, 2, 5 }
Returns: 6
The entire sequence is a zig-zag sequence.
{ 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 }
Returns: 7
There are several subsequences that achieve this length. One is 1,17,10,13,10,16,8.
{ 10, 20 }
Returns: 2
{ 20, 10 }
Returns: 2
{ 20, 20 }
Returns: 1
Submissions are judged against all 38 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ZigZag with a public method int longestZigZag(vector<int> sequence) · 38 test cases · 2 s / 256 MB per case