Make an array with the differences i.e. diff[i] = list[i+1] - list[i]
Iterate through the array diff and find out the sign changes.
The total number of the sign changes will be the length of the
largest sub-sequence which is zig-zag.
Order: O(n) Space: O(n).
On Friday, June 8, 2012 3:47:46 PM UTC+5:30, Ratan wrote:
>
> Given a list of integers n, we have to find the length of largest
> zigazg subsequence in the list.... i.e,zigzag subsequence is defined
> as "if the first number is increasing then the 2nd one should be
> decreasing or vice versa...... "
>
> for eg : if list[n]={1,10,5,9,8,12,20} then,
>
> largest zigzag subsequence will be : {1,10,5,9,8,12} or
> {1,10,5,9,8,20} and length will be=6;
>
>
> --
> --
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/--cJ1MjAH_8J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
