complexity of this algo is O(n) ..I guess it is better than dynamic
programming approach which is O(n^2).
On Sat, Dec 17, 2011 at 6:28 PM, atul anand <atul.87fri...@gmail.com> wrote:
> please see the algo and let me know if i am doing it wrong:-
>
> toggle= arr[i+1] > arr[i];
> subseq=0;
>
> for( i=0 ; i<len ;i++)
> {
>
> if ( toggle == 1)
> {
> if( arr[i+1] > arr[i])
> {
> subseq=subseq+2;
>
> }
>
> toggle=0;
> }
> else
> {
>
> if(arr[i] > arr[i+1])
> {
>
> subseq=subseq+2;
>
> }
>
> toggle=1;
> }
>
>
> }
>
> print subseq;
>
>
> On Fri, Dec 16, 2011 at 10:33 AM, Sangeeta <sangeeta15...@gmail.com>wrote:
>
>> 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
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> 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.
>>
>>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
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.
