@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 <usrivastav...@gmail.com
> 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 <atul.87fri...@gmail.com>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 <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.
>>
>
>
>
> --
> *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 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.
