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.
