@Ankur :
yeah rite it wont work.... i have modified my algo and used many test cases
, it is giving rite output.
could you catch any test case for which it would fail.
here is the updated code :-
#include<stdio.h>
int findSeqLen(int arr[],int len,int subseq)
{
int i=0,flag1,flag2,toggle;
int lastIndex=0;
toggle=arr[i+1] > arr[i];
flag1=toggle;
flag2=!flag1;
if(len <= 2)
{
return 0;
}
for(i=0;i<len;i++)
{
if(i==len-1)
{
break;
}
if(toggle==1)
{
if(arr[i+1] > arr[i] && arr[lastIndex] < arr[i+1] && flag1==1)
{
subseq++;
flag1=0;
flag2=1;
toggle=0;
lastIndex=i+1;
}
printf("\n\nin toggle = 1");
printf("\n i = %d , lastIndex = %d , subseq =
%d",i,lastIndex,subseq);
}
else
{
if(arr[i] > arr[i+1] && arr[lastIndex] > arr[i+1] && flag2==1)
{
subseq++;
flag2=0;
flag1=1;
toggle=1;
lastIndex=i+1;
}
printf("\n\nin toggle = 0");
printf("\n i = %d , lastIndex = %d , subseq =
%d",i,lastIndex,subseq);
}
}
return subseq;
}
int main()
{
int arr[80],i,j,n,ls=1;
printf("\nNumber of elements to be entered = ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\nEnter Number = ");
scanf("%d",&arr[i]);
}
ls=findSeqLen(arr,n,ls);
printf("\n\nSubsequence len = %d\n\n",ls);
}
On Mon, Dec 19, 2011 at 1:19 AM, Ankur Garg <[email protected]> wrote:
> @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 <[email protected]> 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 <[email protected]>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 <[email protected]>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 <[email protected]>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 [email protected].
>>>>> To unsubscribe from this group, send email to
>>>>> [email protected].
>>>>> 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 [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
