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.
Definition
- Class:
- ZigZag
- Method:
- longestZigZag
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int longestZigZag(int[] sequence)
- (be sure your method is public)
Constraints
- sequence contains between 1 and 50 elements, inclusive.
- Each element of sequence is between 1 and 1000, inclusive.
Examples
{ 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
{ 44 }
Returns: 1
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }
Returns: 2
{ 10, 9, 8, 7, 6, 7, 8, 9, 10 }
Returns: 3
{ 12, 333, 700, 436, 1, 919, 959, 456, 456, 456, 1000, 193, 192, 13, 75, 818, 197, 197, 2, 777, 99, 81, 222, 109, 1000, 19, 27, 270, 62, 189, 987, 234, 55, 2, 718, 238, 901, 901, 900, 432, 55, 606, 89, 7, 7, 23, 789, 790, 800, 1000 }
Returns: 26
{ 70, 55, 13, 2, 99, 2, 80, 80, 80, 80, 100, 19, 7, 5, 5, 5, 1000, 32, 32 }
Returns: 8
{ 3, 3, 3, 3, 3 }
Returns: 1
{ 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2 }
Returns: 3
{ 1,2,2,1,1,2,3,3,2,1,1,2,3,4,4,3,2,1,1,2,3,4,5,5,4,3,2,1 }
Returns: 9
{ 396, 549, 22, 819, 611, 972, 730, 638, 978, 342, 566, 514, 752, 871, 911, 172, 488, 542, 482, 974, 210, 474, 66, 387, 1, 872, 799, 262, 567, 113, 578, 308, 813, 515, 716, 905, 434, 101, 632, 450, 74, 254, 1000, 780, 633, 496, 513, 772, 925, 746 }
Returns: 37
{ 374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 249, 22, 176, 279, 23, 22, 617, 462, 459, 244 }
Returns: 36
{ 89, 106, 125, 142, 141, 137, 158, 184, 191, 189, 189, 206, 228, 240, 228, 263, 259, 256, 266, 287, 302, 297, 330, 341, 353, 353, 364, 376, 365, 398, 386, 420, 413, 419, 451, 441, 463, 484, 480, 487, 494, 520, 534, 542, 534, 541, 571, 584, 565, 577 }
Returns: 26
{ 61, 82, 126, 97, 167, 186, 119, 154, 155, 142, 153, 181, 172, 192, 223, 272, 273, 260, 280, 330, 329, 350, 273, 324, 349, 306, 385, 375, 420, 416, 435, 457, 373, 477, 395, 487, 500, 439, 493, 537, 518, 549, 542, 500, 524, 541, 512, 589, 549, 543 }
Returns: 35
{ 8, 6, 4, 2, 3, 5, 7, 9 }
Returns: 3
{ 4, 1, 6, 7, 7, 8, 9, 8, 6, 8 }
Returns: 5
{ 4, 6, 4, 4, 1, 2, 6, 7, 1, 3 }
Returns: 6
{ 9,1,8,2,7,3,6,4,5,5,4,6,3,7,2,8,1,9 }
Returns: 17
{ 251, 742, 766, 540, 943, 591, 486, 22, 47, 362, 990, 744, 936, 347, 296, 362 }
Returns: 10
{ 245, 467, 483, 930, 576, 516, 46, 897, 195, 758, 332, 895, 531, 600, 456, 203 }
Returns: 11
{ 949, 890, 206, 768, 74, 912, 402, 158, 353, 957, 840, 148, 813, 182, 752, 240 }
Returns: 12
{ 392, 898, 775, 732, 581, 103, 557, 298, 908, 609, 248, 105, 757, 782, 374, 159 }
Returns: 9
{ 660, 474, 928, 777, 518, 449, 146, 232, 849, 976, 927, 600, 928, 655, 939, 610 }
Returns: 10
{ 9,10,1,5,9,2,8,9,10,4,10,1,7,4,7,1,9,9,9,9,6,9,6,8,3,1,8,5,3,9,6 }
Returns: 23
{ 8,3,6,3,8,10,3,5,1,9,4,8,8,7,5,5,3,2,3,8,9,4,5,4,9,8,8,5,7,1,2 }
Returns: 21
{ 5,7,9,5,3,6,6,7,4,7,7,7,4,10,5,2,2,5,6,9,8,1,3,7,8,3,2,1,10,9,9 }
Returns: 15
{ 2,4,5,10,4,7,4,1,10,10,7,10,8,2,7,9,4,10,3,8,2,6,9,6,9,9,1,1,5,1,9 }
Returns: 22
{ 3,8,1,5,3,10,2,7,3,1,9,3,3,9,8,4,7,6,8,7,2,5,5,10,8,1,7,4,5,2,6 }
Returns: 24
{ 5,10,7,4,5,3,8,7,4,5,5,2,2,1,4,3,7,5,1,5,7,10,2,10,9,3,9,1,6,1,2 }
Returns: 22
{ 1,8,2,3,5,1,1,7 }
Returns: 6
{ 5,8,3,5,4,5,2,3 }
Returns: 8
{ 9,10,7,8,4,1,8 }
Returns: 6
{ 6,4,2,8,3,5,8 }
Returns: 5
{ 1000 }
Returns: 1
{ 1, 1 }
Returns: 1