@Atul ur solution is wrong
It seems u r comparing just the neighbouring elements .
The question is not to find the contiguous zig-zag sequence but longest
subsequence
Also even in case of contiguous sequence ur solution will not print the
correct length
like for 6 7 4 ur solution will print answer as 4 whereas in the answer
should be 3
Regards
Ankur
On Mon, Dec 19, 2011 at 1:16 AM, Ankur Garg <ankurga...@gmail.com> wrote:
> a linear solution for this problem . although its more than O(n) but will
> never be O(n*2)..used DP to solve it
>
> space used -O(2n)
>
> int ZigZagLength(vector<int> a){
> int n=a.size();
> int DP[n][2];
> DP[0][0]=1;
> DP[0][1]=0;
> DP[1][0]=2;
> DP[1][1]=0;
> int j;
> for(int i=2;i<n;i++){
> if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])==0){
> DP[i][0]=DP[i-1][0];
> DP[i][1]= i-1;
> }
> if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])<0){
> DP[i][0]=DP[i-1][0]+1;
> DP[i][1]= i-1;
> }
> else{
> j = DP[i-1][1];
> while(j>0){
> if((a[i]-a[j])*(a[j]-a[DP[j][1]])<0){
> DP[i][0]=max(DP[j][0]+1,DP[i-1][0]);
> if(DP[i][0]==DP[j][0]+1)
> DP[i][1]=j ;
> else
> DP[i][1]= i-1;
> break;
> }else
> j= DP[j][1];
> }
> if(j==0){
> DP[i][0]=DP[i-1][0];
> DP[i][1]=DP[i-1][1];
> }
> }
> }
> return DP[n-1][0];
> }
>
> On Sun, Dec 18, 2011 at 11:04 AM, atul anand <atul.87fri...@gmail.com>wrote:
>
>> 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.
>>
>
>
--
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.
