hi i gave anser of longets sequence if there are more than one then I only print one
On Tue, Dec 20, 2011 at 12:31 PM, atul anand <[email protected]>wrote: > @UTKARSH : > > it should be 1 4 3 7 6 > > why are you skipping 3 even when 143 is in zig zag sequence. > > On Tue, Dec 20, 2011 at 11:26 AM, UTKARSH SRIVASTAV < > [email protected]> wrote: > >> hi i want to know whether this is right >> suppose array is : 1,4,3,2,7,8,6,2 >> we just find where sign changes and take the first element of sign change >> and we can take last element. >> 1<4>3>2<7<8>6>2 >> so answer should be 1 4 2 8 2 >> correct me if i am wrong >> >> On Mon, Dec 19, 2011 at 12:26 PM, atul anand <[email protected]>wrote: >> >>> @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. >>> >> >> >> >> -- >> *UTKARSH SRIVASTAV >> CSE-3 >> B-Tech 3rd Year >> @MNNIT ALLAHABAD* >> >> >> -- >> 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. > -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT ALLAHABAD* -- 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.
