@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 <ankurga...@gmail.com> 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 <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. > -- 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.