StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>U can do it in <strong>O(n)</strong> using a <strong>greedy</strong> approach. Take the first non-repeating number - this is the first number of your zigzag subsequence. Check whether the next number in the array is lesser than or greater than the first number. </p> <p><strong>Case 1:</strong> If <strong>lesser</strong>, check the next element to that and keep going till you find the least element (ie) the element after that would be greater than the previous element. This would be your second element.</p> <p><strong>Case 2:</strong> If <strong>greater</strong>, check the next element to that and keep going till you find the greatest element (ie) the element after that would be lesser than the previous element. This would be your second element.</p> <p>If u have used Case 1 to find the second element, use Case 2 to find the third element or vice-versa. Keep alternating between these two cases till u have no more elements in the original sequence. The resultant numbers u get would form the longest zigzag subsequence.</p> <p><strong>Eg: { 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 }</strong></p> <p>The resulting subsequence:</p> <p><strong>1 -> 1,17 (Case 2) -> 1,17,5 (Case 1) -> 1,17,5,15 (Case 2) -> 1,17,5,15,5 (Case 1) -> 1,17,5,15,5,16 (Case 2) -> 1,17,5,15,5,16,8 (Case 1)</strong> </p> <p>Hence the length of the longest zigzag subsequence is 7.</p> <p>U can refer to sjelkjd's <a href="http://community.topcoder.com/stat?c=problem_solution&cr=107835&rd=4493&pm=1259" rel="noreferrer">solution</a> for an implementation of this idea.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload